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

#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;
}

Application Areas

• network algorithms, for example, single source shortest path
• geometric algorithms, for example, plane sweep for line segment intersection

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

Disadvantages

• 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

See also:

Other data types with key of linearly ordered type:

Dictionary Arrays

Dictionaries.

Sorted Sequences.

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

User Defined Parameter Types

LEDA Item Concept

Linear Orders

Hashed Types