Definition
An instance Q of the parameterized data type priority_queue<K,I> is a collection of items (type pqitem). Every item contains a key from type K and an information from the linearly ordered type I. K is called the key type of Q and I is called the information type of Q. The number of items in Q is called the size of Q. If Q has size zero it is called the empty priority queue. We use <k, i > to denote a pqitem with key k and information i.
The type priority_queue<K,I> is identical to the type pqueue except that the meanings of K and I are interchanged. We now believe that the semantics of pqueue is the more natural one and keep priority_queue<K,I> only for historical reasons. We recommend to use pqueue instead.
#include < LEDA/prio.h >
Creation
priority_queue<K,I> | Q | creates an instance Q of type priority_queue<K,I> and initializes it with the empty priority queue. |
Operations
K | Q.key(pq_item it) | returns the key of item it.
Precondition: it is an item in Q. |
I | Q.inf(pq_item it) | returns the information of item it.
Precondition: it is an item in Q. |
pq_item | Q.insert(K k, I i) | adds a new item <k, i > to Q and returns it. |
pq_item | Q.find_min() | returns an item with minimal information (nil if Q is empty). |
K | Q.del_min() | removes the item it = Q.find_min() from Q
and returns the key of it.
Precondition: Q is not empty. |
void | Q.del_item(pq_item it) | removes the item it from Q.
Precondition: it is an item in Q. |
void | Q.change_key(pq_item it, K k) | |
makes k the new key of item it.
Precondition: it is an item in Q. |
||
void | Q.decrease_inf(pq_item it, I i) | |
makes i the new information of item it.
Precondition: it is an item in Q and i is not larger then inf (it). |
||
int | Q.size() | returns the size of Q. |
bool | Q.empty() | returns true, if Q is empty, false otherwise |
void | Q.clear() | makes Q the empty priority queue. |
Implementation
Priority queues are implemented by Fibonacci heaps [32]. Operations insert, del_item, del_min take time O(log n), find_min, decrease_inf, key, inf, empty take time O(1) and clear takes time O(n), where n is the size of Q. The space requirement is O(n).
Example
Dijkstra's Algorithm (cf. section Graph and network algorithms)