aGrUM  0.13.2
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:

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);

Classes

class  gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >
 A MultiPriorityQueue is a heap in which each element has a mutable priority and duplicates are allowedA priority queue is quite similar to a heap except that a priority (a score) is assigned to each element in the structure. More...
 
class  gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >
 The internal class for representing priority queues. More...
 
class  gum::PriorityQueue< Val, Priority, Cmp, Alloc >
 A priorityQueue is a heap in which each element has a mutable priorityA priority queue is quite similar to a heap except that a priority (a score) is assigned to each element in the structure. More...