Back to Study Material Data Structures and Algorithms

Priority Queue

A priority queue is an abstract data type where each element has an associated priority and the element with the highest (or lowest) priority is always deq...

Priority Queue

Priority Queues and the Heap Data Structure

A priority queue is an abstract data type where each element has an associated priority and the element with the highest (or lowest) priority is always dequeued first, regardless of insertion order. Unlike a regular queue that serves elements in arrival order, a priority queue serves the most urgent element first.

The most common implementation is a binary heap, specifically a min-heap for a minimum priority queue or a max-heap for a maximum priority queue. A binary heap is a complete binary tree where every parent node has a priority less than or equal to its children (min-heap) or greater than or equal to its children (max-heap). Complete means all levels are fully filled except possibly the last, which is filled from left to right.

Binary heaps are stored efficiently in arrays without explicit pointers. For a node at index i (using one-based indexing), the left child is at 2i, the right child is at 2i plus one, and the parent is at floor(i divided by 2). With zero-based indexing, the left child is at 2i plus one, the right child is at 2i plus two, and the parent is at floor((i minus one) divided by two).

Insert adds the new element at the end of the array (the next available position in the last level) and then bubbles it up by repeatedly swapping it with its parent if it violates the heap property. This process is called sift-up or heapify-up and takes O(log n) time because the tree height is logarithmic.

Extract-min (or extract-max) removes the root, which holds the minimum, replaces it with the last element in the array, removes that last position, and then bubbles the new root down by swapping with the smaller of its two children until the heap property is restored. This sift-down operation also takes O(log n) time. Peek returns the root in O(1) time without modification.

Worked example: insert 5, 3, 7, 1 into a min-heap. After all inserts, the heap root is 1. Extract-min returns 1; 7 moves to root, sifts down, 3 becomes root. Extract-min returns 3. Remaining heap has root 5 or 7 depending on structure.

Interview tip: when a problem asks for the k largest or k smallest elements in a stream, state that a heap of size k gives O(n log k) time, which is much better than sorting the entire input at O(n log n).

Heap Operations: Insert, Extract, and Heapify

Building a heap from an unsorted array naively by inserting elements one at a time takes O(n log n) time. The heapify algorithm builds a heap in O(n) time by applying sift-down from the bottom up, a non-obvious result that follows from the geometric distribution of nodes at each level.

The heapify algorithm starts at the last non-leaf node, which is at index floor(n divided by 2) in one-based indexing (or floor(n divided by 2) minus one in zero-based indexing), and calls sift-down on it. Then it moves to the previous index and repeats, continuing until index one (the root) is processed. Each sift-down operation takes time proportional to the height of the node being processed. Nodes near the bottom (the majority of nodes) have small heights, so their sift-downs are cheap. The total work sums to O(n) by the geometric series analysis of binary tree heights.

The decrease-key operation reduces the priority of an existing element in a min-heap (or increases it in a max-heap). After changing the value, sift-up is called because the element may now be smaller than its parent. Decrease-key requires knowing the element's current index in the heap array, which means maintaining an external index map updated during all swaps. This is essential for Dijkstra's shortest path algorithm, which repeatedly performs decrease-key as shorter paths are discovered.

The increase-key operation raises the priority of an element. After changing the value, sift-down is called because the element may now be larger than its children.

Space complexity for a heap is O(n). All heap operations that modify the structure take O(log n) time due to the tree height. Heapify runs in O(n). Peek (read the root) is O(1).

Worked example: build a min-heap from array [4, 10, 3, 5, 1]. Length 5, last non-leaf at index 2 (one-based). Sift-down index 2 (value 3): children are at 4 and 5, values 5 and 1. Swap 3 and 1. Array: [4, 10, 1, 5, 3]. Sift-down index 1 (value 4): children are at 2 and 3, values 10 and 1. Swap 4 and 1. Array: [1, 10, 4, 5, 3]. Sift-down 4 at index 3: children at 6 and 7, none exist. Done. Heap: [1, 10, 4, 5, 3].

Interview tip: the O(n) heapify result surprises many candidates. If asked about it, explain that most nodes are near the bottom of the tree and have very short sift-down paths. This insight also generalizes to understanding why building balanced trees bottom-up is typically more efficient than top-down insertion.

Priority Queue Applications: Dijkstra, Huffman, and Top-K

Priority queues are at the core of several fundamental algorithms. Understanding why each algorithm requires a priority queue deepens your appreciation for when to choose this data structure over simpler alternatives.

Dijkstra's single-source shortest path algorithm finds minimum-cost paths from a source node to all other nodes in a weighted graph with non-negative edge weights. A min-heap stores (distance, node) pairs. Initialize with (0, source). Repeatedly extract the node with the smallest tentative distance, then relax its outgoing edges: if the current node's distance plus the edge weight is less than the neighbor's recorded distance, update the neighbor's distance and enqueue (new_distance, neighbor). The heap ensures that the nearest unvisited node is always processed first. With a binary heap, the algorithm runs in O((V + E) log V) time.

Huffman coding builds an optimal prefix-free binary encoding of symbols based on their frequencies. Sort all symbols by frequency and insert them into a min-heap. Repeatedly extract the two nodes with the lowest frequencies, create a new internal node whose frequency is their sum, and enqueue the new node. Continue until one node remains; it is the root of the Huffman tree. The resulting encoding gives the shortest expected codeword length across all symbols. The algorithm runs in O(n log n) time for n symbols.

The top-K elements problem asks for the K largest values in an unsorted array of n elements. The approach: maintain a min-heap of size K. For each element, if the heap has fewer than K elements, insert the element. Otherwise, if the element is larger than the heap's minimum (the root), replace the minimum with the new element (extract-min then insert). After processing all elements, the heap contains the K largest. Time complexity is O(n log K), significantly faster than sorting the full array when K is much smaller than n.

Worked example for top-3: array [7, 10, 4, 3, 20, 15], K=3. Insert 7, 10, 4 into min-heap: [4, 10, 7]. Process 3: 3 < 4 (min), skip. Process 20: 20 > 4, replace. Heap: [7, 10, 20]. Process 15: 15 > 7, replace. Heap: [10, 20, 15]. Top 3: {10, 15, 20}.

Interview tip: for top-K problems, note that a max-heap of all n elements and K extract-max operations gives O(n + K log n). Whether min-heap of size K or max-heap of all elements is faster depends on whether K is small compared to n. Mention both approaches and compare them.