Snippet - PriorityQueue Collection class

PriorityQueue Collection class

The PriorityQueue is a queue to which items can be enqueued in any order and later those items can be dequeued in order of the priority of the items.

The relative priority is defined by a predicate function which is passed to the constructor of the PriorityQueue to determine which one item has the higher priority.

Performance characteristics:
Enqueue and Dequeue are O(log n) operations.
Peek is a O(1) operation.
Contains is a O(n) operation

Use:
Priority queues are used in many situations. Some examples include

Graph algorithms used for path finding require an efficient priority queue to ensure that they work efficiently.

Huffman compression uses a priority queue to build optimal bit patterns used to represent longer frequently occurring patterns.

Simulation and scheduling algorithms often rely on priority queues.

1 Like