Priority Queue Data Structure

A priority queue is a collection in which every element has a priority, and the element with the best priority is always the next one out. It is the tool to reach for whenever "most important first" matters more than "first come, first served": scheduling, simulations, and graph algorithms such as Dijkstra's and Prim's.

This tutorial explains what a priority queue is, how priorities are assigned, how it can be implemented, and where it is used.

What is a Priority Queue in Data Structure?

A priority queue stores elements together with a priority. Its removal operation does not return the oldest element, as an ordinary FIFO queue does, but the element with the highest priority.

For example, an operating system can keep runnable processes in a priority queue so that urgent work runs before background work, and Dijkstra's algorithm keeps unvisited vertices in a priority queue keyed by their current distance so that it always expands the closest one next.

Characteristics of a priority queue:

• Every element has a priority.
• Removal always returns an element with the best priority.
• The order among elements with equal priority is not defined by the abstract data type. Java's PriorityQueue breaks such ties arbitrarily; if equal elements must leave in arrival order, include an insertion counter in the comparison.

Assigning priority in a priority queue

Often the element's own value is its priority. In a max-priority queue the largest value comes out first; in a min-priority queue the smallest value comes out first (Java's PriorityQueue is a min-priority queue by default). For objects, a Comparator can define any priority you need, such as a task's deadline or a customer's tier.

Priority Queue Implementation

A priority queue can be built on an unsorted array, a sorted array, a linked list, a balanced binary search tree or a binary heap. The choice decides which operation is cheap:

A binary heap is the usual choice because both insertion and removal are logarithmic. The simple example below uses a sorted array instead, which is easier to follow: it is a min-priority queue in which the array is kept in descending order, so the smallest (highest-priority) value is always at the end and can be removed in O(1).

// A min-priority queue of int values: the smallest value has the highest priority.
// The array is kept sorted from largest (index 0) to smallest (index count - 1),
// so the highest-priority element is always at the end.
public class SortedArrayPriorityQueue {
  private final int[] items;
  private int count;

  public SortedArrayPriorityQueue(int capacity) {
    items = new int[capacity];
    count = 0;
  }

  public boolean isEmpty() {
    return count == 0;
  }

  public boolean isFull() {
    return count == items.length;
  }

  // Inserts a value in its sorted place: O(n), smaller values shift right
  public void insert(int value) {
    if (isFull()) {
      throw new IllegalStateException("Priority queue is full");
    }
    int i = count - 1;
    // Move every value smaller than the new one one place to the right
    while (i >= 0 && items[i] < value) {
      items[i + 1] = items[i];
      i--;
    }
    items[i + 1] = value;
    count++;
  }

  // Removes and returns the smallest value: O(1)
  public int remove() {
    if (isEmpty()) {
      throw new IllegalStateException("Priority queue is empty");
    }
    return items[--count];
  }

  // Returns the smallest value without removing it: O(1)
  public int peek() {
    if (isEmpty()) {
      throw new IllegalStateException("Priority queue is empty");
    }
    return items[count - 1];
  }

  public static void main(String[] args) {
    SortedArrayPriorityQueue queue = new SortedArrayPriorityQueue(5);
    queue.insert(25);
    queue.insert(55);
    queue.insert(45);
    queue.insert(35);
    queue.insert(15);

    if (queue.isFull()) {
      System.out.println("Queue is full.");
    }

    System.out.println("Element removed from the Priority Queue: " + queue.remove());
    System.out.println("Element at front: " + queue.peek());

    System.out.print("Remaining elements in priority order: ");
    while (!queue.isEmpty()) {
      System.out.print(queue.remove() + " ");
    }
    System.out.println();
  }
}

Queue is full.
Element removed from the Priority Queue: 15
Element at front: 25
Remaining elements in priority order: 25 35 45 55

Applications of Priority Queue

• Task scheduling: jobs with a higher priority (or an earlier deadline) run first.
• Event-driven simulation: events are processed in order of their scheduled time.
• Dijkstra's algorithm: repeatedly picks the unvisited vertex with the smallest known distance.
• Prim's algorithm: repeatedly picks the cheapest edge that connects a new vertex to the growing minimum spanning tree.
• Top-k problems: finding the k largest or most frequent items with a heap of size k.
• Merging k sorted lists and Huffman coding, which repeatedly combine the smallest items.