Definition
An instance Q of the parameterized data type p_queue<P,I> is a collection of items
(type pq_item). Every item contains a priority from a linearly ordered type
P and an information from an arbitrary type I. P is called the priority
type of Q and I is called the information type of Q. If P is a user-defined
type, you have to define the linear order by providing the compare
function (see Section User Defined Parameter Types). 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 < p, i > to denote a pq_item with priority p and
information i.
Remark: Iteration over the elements of Q using iteration macros such as forall
is not supported.
#include < LEDA/core/p_queue.h >
Types
p_queue<P,I>::item | the item type. |
p_queue<P,I>::prio_type | the priority type. |
p_queue<P,I>::inf_type | the information type. |
Creation
p_queue<P,I> | Q | creates an instance Q of type p_queue<P,I> based on the linear order defined by the global compare function compare(const P&, const P&) and initializes it with the empty priority queue. |
p_queue<P,I> | Q(int (*cmp)(const P& , const P& )) | |
creates an instance Q of type p_queue<P,I> based on the linear order defined by the compare function cmp and initializes it with the empty priority queue. Precondition cmp must define a linear order on P. |
Operations
Implementation
Priority queues are implemented by binary heaps [91]. Operations insert, del_item, del_min take time O(log n), find_min, decrease_p, prio, 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)