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)