Old-Style Priority Queues (priority_queue)

Definition

An instance Q of the parameterized data type priority_queue<K,I> is a collection of items (type pq_item). 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 pq_item with key k and information i.

The type priority_queue<K,I> is identical to the type p_queue except that the meanings of K and I are interchanged. We now believe that the semantics of p_queue is the more natural one and keep priority_queue<K,I> only for historical reasons. We recommend to use p_queue instead.

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)