Queue

Priority Queue

What is a Priority Queue?

A priority queue throws out the "first come, first served" rule that a normal queue follows. Every element carries a priority, and whichever element has the most urgent priority gets dequeued next; it doesn't matter how long it's been sitting there.

Key Characteristics

Priority queues have these fundamental properties:

  1. Priority-based ordering:
    • Elements are processed by priority (highest first or lowest first)
  2. Two core operations:
    • insert(item, priority) - Add with priority
    • extractMax()/extractMin() - Remove highest/lowest priority item
  3. Peek operation:
    • View highest/lowest priority item without removal
  4. No FIFO guarantee:
    • Equal priority elements may be processed in arbitrary order

How Does It Work?

A priority queue does not keep its elements fully sorted — that would be far more work than the job needs. It only maintains one weaker rule: every parent outranks its children. That is a binary heap, and it is enough to guarantee the most urgent item is always at the root. Below, the tree and the array underneath it are the same six values — a node at index i keeps its children at 2i + 1 and 2i + 2:

  1. A max-heap holding priorities 9, 7, 8, 3, 5. Every parent outranks its children, so the most urgent item is always at the root.
    97835stored as an array907182335456
  2. insert(10): the new item is appended to the end of the array — index 5, whose parent is index 2 holding 8. 10 outranks 8, so the heap rule is broken.
    9783510stored as an array90718233541056
  3. Swap them. 10 is now at index 2, and its new parent is the root, 9 — still out of order, so it keeps climbing.
    9710358stored as an array90711023354856
  4. Swap again and 10 reaches the root. Two swaps for six elements — the climb is bounded by the height of the tree, not its size.
    1079358stored as an array10071923354856
  5. peek(): read the root. It is the highest priority by construction, so no searching is needed — this is the O(1) operation.
    1079358stored as an array10071923354856
  6. extractMax(): 10 is returned and the last element, 8, is moved into the empty root. Now the root is too small, so it has to sink instead.
    87935stored as an array807192335456
  7. The larger child, 9, is promoted. The heap rule holds again and the queue is ready to serve the next highest priority.
    97835stored as an array907182335456
Being compared or swappedRead by peekHighest priority, heap validWaiting

Both repair routines — climbing after an insert, sinking after an extract — only ever move along one path from root to leaf. That path is the height of the tree, so doubling the number of items adds just one extra step.

Time Complexity

For the usual binary heap implementation:

  • insert(): O(log n)
  • extractMax()/extractMin(): O(log n)
  • peek(): O(1)
  • isEmpty(): O(1)

This is the one queue type whose curve is not flat. The lower line is peek, which just reads the root. The upper line is insert and extract, which walk the height of the tree — still shallow, since 1,000 items are only about 10 levels deep:

Implementation Variations

Common implementation approaches:

  1. Binary Heap:
    • Most common implementation
    • O(log n) insert and extract
    • O(1) peek
    • Memory efficient
  2. Balanced Binary Search Tree:
    • O(log n) all operations
    • Supports more operations (like delete-by-value)
    • Higher memory overhead
  3. Array (Unsorted):
    • O(1) insert, O(n) extract
    • Simple but inefficient for large datasets
  4. Fibonacci Heap:
    • Amortized O(1) insert
    • O(log n) extract
    • Complex implementation

Applications

Priority queues are used in:

  • Dijkstra's Algorithm: Finding shortest paths in graphs
  • Huffman Coding: Data compression
  • Operating Systems: Process scheduling
  • Event-driven Simulation: Processing events in time order
  • A* Search: Pathfinding in AI
  • Bandwidth Management: Prioritizing network packets

Special Cases

Interesting priority queue variations:

  • Min-Priority Queue: Extracts minimum priority first
  • Max-Priority Queue: Extracts maximum priority first
  • Double-Ended Priority Queue: Supports both min and max extraction
  • Indexed Priority Queue: Allows priority updates by key
  • Bounded Priority Queue: Fixed capacity with eviction policies

What makes it so useful is that it always hands you the most important item on demand, which is exactly what a lot of algorithms need. Under the hood it's usually built on a heap, though a balanced BST works too, and which one you pick depends on how the application balances insertion speed against extraction speed.

Daily DSA Challenge by Scale Engineer

Min-Priority Queue Visualiser (lower number = higher priority)

Priority queue is empty

Test Your Knowledge before moving forward!

Priority Queue Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Priority Queue Implementation

// Priority Queue Implementation in JavaScript (Min-Heap)
class PriorityQueue {
  constructor(comparator = (a, b) => a.priority - b.priority) {
    this.heap = [];
    this.comparator = comparator;
  }

  // Add element to the queue
  enqueue(value, priority) {
    const element = { value, priority };
    this.heap.push(element);
    this.bubbleUp(this.heap.length - 1);
  }

  // Remove and return the highest priority element
  dequeue() {
    if (this.isEmpty()) return null;
    const root = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return root.value;
  }

  // Peek at the highest priority element without removing it
  peek() {
    if (this.isEmpty()) return null;
    return this.heap[0].value;
  }

  // Get current size of the queue
  size() {
    return this.heap.length;
  }

  // Check if the queue is empty
  isEmpty() {
    return this.heap.length === 0;
  }

  // Move element up the heap to maintain heap property
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.comparator(this.heap[index], this.heap[parentIndex]) >= 0) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  // Move element down the heap to maintain heap property
  bubbleDown(index) {
    const lastIndex = this.heap.length - 1;
    while (true) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      let smallestIndex = index;

      if (leftChildIndex <= lastIndex && 
          this.comparator(this.heap[leftChildIndex], this.heap[smallestIndex]) < 0) {
        smallestIndex = leftChildIndex;
      }

      if (rightChildIndex <= lastIndex && 
          this.comparator(this.heap[rightChildIndex], this.heap[smallestIndex]) < 0) {
        smallestIndex = rightChildIndex;
      }

      if (smallestIndex === index) break;
      [this.heap[index], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[index]];
      index = smallestIndex;
    }
  }
}

// Usage
const pq = new PriorityQueue();
pq.enqueue("Task 1", 3);  // Lower numbers = higher priority
pq.enqueue("Task 2", 1);
pq.enqueue("Task 3", 2);

console.log(pq.dequeue()); // "Task 2" (highest priority)
console.log(pq.peek());    // "Task 3" (next highest priority)
console.log(pq.size());    // 2

Done With the Learning

Mark Priority Queue as done and view it on your dashboard

Explore Other Types

Single Ended Queue

Circular Queue

Double-Ended Queue

Multiple Queue