Priority queue

This file provides class MultiPriorityQueue that is essentially a heap in which elements are sorted according to a dynamically modifiable priority. More...

Collaboration diagram for Priority queue:

Classes
class	gum::MultiPriorityQueue< Val, Priority, Cmp >
	A MultiPriorityQueue is a heap in which each element has a mutable priority and duplicates are allowed. More...
class	gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >
	The internal class for representing priority queues. More...
class	gum::PriorityQueue< Val, Priority, Cmp >
	A priorityQueue is a heap in which each element has a mutable priority. More...
class	gum::SortedPriorityQueue< Val, Priority, Cmp >
	A priority queue in which we can iterate over the elements from the top to bottom or conversely. More...

Detailed Description

This file provides class MultiPriorityQueue that is essentially a heap in which elements are sorted according to a dynamically modifiable priority.

As in heaps, elements are sorted according to a weak order which is < by default, i.e., the top element of the queue is the smallest element and the more to the bottom the greater the element.

Usage example:

// create a priority queue of strings, the priorities of which are integers
// the element at the top of the queue has the smallest priority
MultiPriorityQueue<std::string> queue1;
 
// insert elements into the queue
queue1.insert (8,  "AAA");
queue1.insert (10, "BBB");
queue1.insert (2,  "CCC");
queue1.insert (23, "DDD");
queue1.insert (24, "EEE");
queue1.insert (10, "AAA");
 
// copy the queue
MultiPriorityQueue<std::string> queue2 = queue1;
 
// initializer list constructor
MultiPriorityQueue<std::string,int>
queue3 { std::pair<std::string,int> ( "aa", 3 ),
         std::pair<std::string,int> ( "bb", 2 ) };
 
// create a priority queue of strings, the priorities of which are pairs of
// int
MultiPriorityQueue< std::string, std::pair<int,int> > queue3;
 
// get the top element, then remove it
std::cerr << queue2.top() << std::endl;
queue2.eraseTop();
 
// get the top element, then remove it
std::cerr << queue2.pop() << std::endl;
 
// output the content of the queue
std::cerr << queue1 << std::endl;
 
// change the priority of the element at position 3
Size new_pos=queue1.setPriorityByPos (3,100);
 
// change the priority of all instances of element "AAA"
queue1.setPriority ("AAA",100);

This file provides class PriorityQueue that is essentially a heap in which elements are sorted according to a dynamically modifiable priority. As in heaps, elements are sorted according to a weak order which is < by default, i.e., the top element of the queue is the smallest element and the more to the bottom the greater the element. In addition, PriorityQueue has a special feature that enables it to prevent multiple identical elements to be stored into it.

Usage example:

// create a priority queue of strings, the priorities of which are integers
// the element at the top of the queue has the smallest priority
PriorityQueue<std::string> queue1;
 
// insert elements into the queue
queue1.insert (8,  "AAA");
queue1.insert (10, "BBB");
queue1.insert (2,  "CCC");
queue1.insert (23, "DDD");
queue1.insert (24, "EEE");
 
// copy the queue
PriorityQueue<std::string> queue2 = queue1;
 
// initializer list constructor
PriorityQueue<std::string,int> queue3 { std::pair<std::string,int> ("aa", 3),
                                        std::pair<std::string,int> ("bb", 2 )
};
 
// create a priority queue of strings, the priorities of which are pairs of
// int
PriorityQueue< std::string, std::pair<int,int> > queue3;
 
// get the top element, then remove it
std::cerr << queue2.top() << std::endl;
queue2.eraseTop();
 
// get the top element, then remove it
std::cerr << queue2.pop() << std::endl;
 
// output the content of the queue
std::cerr << queue1 << std::endl;
 
// change the priority of the element at position 3
Size new_pos=queue1.setPriorityByPos (3,100);
 
// change the priority of all instances of element "AAA"
queue1.setPriority ("AAA",100);