Algorithmic Solutions > LEDA > LEDA Guide > Simple,Basic, and Advanced Data Types > Advanced Data Types > Priority Queues

Priority Queues

The data type p_queue can be used to store objects of an arbitrary type I together with an associated priority of a linearly ordered type P (int, string, …). The elements of a `p_queue` are of type `pq_item`.

In a Priority Queue the object with the minimum priority can be accessed very efficiently.

Example

The following program reads a sequence of doubles from standard input (cin) and stores them in a Priority Queue. The priority type is double and the information type is int. (The information type is not used in the example.) Then it repeatedly extracts the minimum element from the queue until the queue is empty. In this way the input sequence is sorted in increasing order.
```#include <LEDA/core/p_queue.h>

int main()
{
leda::p_queue<double,int> Q;
//priority type double, information type is irrelevant

std::cout << "Please insert double numbers";  std::cout << "('.'+'Return' stops loop):\n";

double x;
while (std::cin >> x) Q.insert(x,0);

while (!Q.empty()) std::cout << Q.del_min() << std::endl;

return 0;
}```

Strengths

• operation `find_min()` is very efficient (O(1) amortized)
• operations `insert()` and `del_min()` are efficient (O(logn) amortized)
• very useful in important application areas
• more efficient than Sorted Sequences (constant factors are smaller)
• more functionality than some related data types

• less functionality than Sorted Sequences
• less efficient than some related data types

Tips

• Use Priority Queues if your main operation is finding the object with minimum priority (key).
• Do not use p_queue if you need direct access to other objects.
• If you want your objects to be sorted automatically use Sorted Sequences.
• Otherwise consider using one of the related data types

Other data types with key of linearly ordered type:

Data types with key of type pointer, item, or int: Maps.

Data types with key of hashed type: Hashing Arrays.

Bounded Priority Queues

Node Priority Queues

Bounded Node Priority Queues

Manual Entries:

Manual Page Priority Queues

LEDA Item Concept

Linear Orders

Hashed Types