Priority Queues

Priority queue is an ADT.

It defines a queue where each element has some priority.

Table of contents
  1. Comparable Fields
  2. Sortedness
  3. Supported Operations
  4. Use Cases

Comparable Fields

To define a sense of priority, there has to be a way to compare each element in the queue.

There are mainly two approaches:

  • Maintain a separate comparable priority field
    • And separate data field

    This approach is more common.

  • Or just use a comparable data field

Sortedness

Regardless of the insertion order, the priority queue maintains a certain order according to the priority.

Defining high priority is deferred until the implementation.

Supported Operations

Core operations:

  • enqueue(data, priority): Add an element to the queue with given priority
  • dequeue(): Remove and return the element with the highest priority
  • peek(): Return the element with the highest priority without removing it

Auxiliary operations:

  • size(): Return the number of elements in the queue
  • isEmpty(): Return true if the queue is empty
  • clear(): Remove all elements from the queue

Use Cases

  • Job scheduling: Assigning tasks to workers based on priority
  • Greedy algorithms
  • Sorting algorithms