Lesson 7 · Non-linear structures

Priority Queues

Priority Queues are abstract data types where elements are dequeued according to their priority, not just their insertion order.

Ordered by Priority, Not Arrival

A priority queue is an abstract data type in which every element carries a priority, and the element removed is always the one with the highest priority — regardless of when it was inserted. It is a queue by interface and not by discipline: it deliberately breaks the FIFO promise that defines an ordinary queue.

The interface is small. insert (or push, enqueue, offer) adds an element with a priority. extract (or pop, poll) removes and returns the highest-priority element. peek (or top) reads it without removing. Some implementations add decrease-key, which lowers an element's priority in place.

The distinction between the abstract type and its implementation matters here more than usual, because the two names get used interchangeably. A priority queue is the contract; a heap is the data structure that almost always implements it. C++ makes this explicit — std::priority_queue is an adaptor built over a container using heap operations.

Notice what the type does not promise. There is no ordering among equal priorities, no way to iterate in priority order without emptying the structure, and no efficient search for an arbitrary element. A priority queue answers one question — what is the most urgent item — and everything else costs O(n).

The everyday model is a hospital emergency room. Patients arrive in one order and are treated in another, determined by severity. A patient arriving later with a more serious condition is seen first, and that inversion is the entire purpose of the structure.

Highest priority leaves first, whenever it arrived
insert, extract, peek — and sometimes decrease-key
The priority queue is the contract; the heap is the usual implementation
No ordering among equal priorities, and no efficient search

Why a Heap and Not Something Simpler

Two obvious implementations each fail on one operation, and comparing them shows what the heap is buying.

An unsorted list makes insertion trivial — append at O(1) — but extraction must scan every element to find the maximum, at O(n). A sorted list inverts this: extraction is O(1) from the end, but insertion must find the correct position and shift, at O(n).

Either is acceptable when one operation dominates heavily. When both are frequent, both are bad — and a binary heap gives O(log n) for each, which is the balanced answer.

A heap is a complete binary tree in which every parent compares at least as favourably as its children. The ordering is deliberately partial: it constrains parent against child only, saying nothing about siblings. That weakness is precisely why updates cost O(log n) — repairing a single root-to-leaf path suffices, where maintaining a total order would cost far more.

Insertion appends at the end and sifts up while it beats its parent. Extraction takes the root, moves the last element into its place, and sifts down, swapping with the better of the two children until both are worse. Each touches one path, hence O(log n).

Because the tree is complete it needs no pointers: stored in an array, the children of index i are at 2i+1 and 2i+2 and the parent at ⌊(i−1)/2⌋. That contiguity makes it markedly more cache-friendly than a pointer-based tree, which is why heaps beat their asymptotics in practice.

Other heaps exist for specific needs. A binomial heap merges two heaps in O(log n); a Fibonacci heap achieves O(1) amortised insert and decrease-key, improving Dijkstra's theoretical bound to O(E + V log V) — though its constant factors are large enough that binary heaps usually win in practice. A d-ary heap widens the branching to trade cheaper decrease-key against costlier extraction.

Implementations of the same interface
Backing	Insert	Extract	Peek
Unsorted list	O(1)	O(n)	O(n)
Sorted list	O(n)	O(1)	O(1)
Binary heap	O(log n)	O(log n)	O(1)
Balanced BST	O(log n)	O(log n)	O(log n)
Fibonacci heap	O(1) amortised	O(log n) amortised	O(1)

Unsorted lists are fast to insert, slow to extract; sorted lists the reverse
A heap balances both at O(log n), with O(1) peek
Partial ordering is what keeps updates to a single path
Array storage means no pointers and good cache behaviour

Ties, Updates, and the Practical Traps

Three details cause most of the bugs, and none of them is about the heap algorithm itself.

Ties are not stable. Two elements of equal priority emerge in an unspecified order — the heap's partial ordering says nothing about siblings. If arrival order should break ties, make the priority a pair: (priority, insertionCounter), with a counter incremented on every push. Comparison then falls through to the counter and the behaviour becomes deterministic.

This also solves a subtler problem in Python and Java. If the priority ties and the payload is not comparable, the comparison falls through to the object itself and raises a TypeError. The counter guarantees the comparison always resolves before reaching the payload.

Decrease-key needs a position index. Dijkstra's algorithm wants to lower a vertex's tentative distance, but a heap offers no way to find that vertex — searching is O(n). Two responses exist. Maintain a position map from element to array index, updated on every swap, giving a true O(log n) decrease-key. Or, far more commonly, push a duplicate entry with the improved priority and discard stale entries when they surface — checking on extraction whether the popped distance still matches the recorded best.

The lazy approach is what most real implementations use. It costs O(E log E) rather than O(E log V) and can hold more entries than vertices, but it avoids maintaining the index map entirely and is much harder to get wrong.

Max heap from a min heap. Most libraries provide only a min heap. Obtain a max heap by negating the priorities on insert and again on extract, or by supplying a reversed comparator where the library allows one. Negation fails on unsigned types and on the minimum representable integer, so the comparator is safer when available.

A final note on complexity: building a heap from n existing elements is O(n), not O(n log n). Sifting down from the last internal node backwards costs less than repeated insertion, because most nodes sit near the bottom where sift-down is cheap. Use the library's heapify rather than a push loop when the data is already available.

Equal priorities emerge in arbitrary order — add a counter to fix it
The counter also prevents comparison falling through to the payload
Lazy duplicates usually beat maintaining a position map for decrease-key
Heapify an existing array in O(n) rather than pushing n times

Key reference

Terms, operations, and practical uses

Core Concepts

Heap PropertyThe invariant stating that a parent node is always ordered before (or equal to) its children, depending on if it is a min-heap or max-heap.
Complete Binary TreeA tree where every level is fully populated except possibly the last level, which is filled from left to right.
Sift-Up / SwimThe operation of moving a newly inserted element up the tree until the heap property is restored.

Heap Operations

Sift-Down / SinkThe operation of moving the root element down the tree (swapping with the smaller/larger child) until the heap property is restored.
HeapifyThe O(N) process of converting an arbitrary array into a valid heap by performing sift-down operations on all non-leaf nodes from bottom to top.
Extract-MinRemoving and returning the root element of a min-heap, followed by replacing it with the last element and sifting down.

Applications

Dijkstra's AlgorithmUses a priority queue to always process the nearest unvisited vertex next, guaranteeing the shortest path.
Huffman CodingRepeatedly extracts the two lowest-frequency trees from a priority queue to build an optimal prefix code tree.
Kth Largest ElementMaintaining a min-heap of size K while iterating through N elements guarantees the root is the Kth largest element in O(N log K) time.

Implementation

Build a min-priority queue

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []
    def push(self, val):
        heapq.heappush(self.heap, val)
    def pop(self):
        return heapq.heappop(self.heap)
pq = PriorityQueue()
for value in (10, 5, 1):
    pq.push(value)
print('Heap array:', pq.heap)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class PriorityQueue {
    public:
    vector<int> heap;
    void push(int val) {
        heap.push_back(val);
        int i = heap.size() - 1;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[i] >= heap[parent]) break;
            swap(heap[i], heap[parent]);
            i = parent;
        }
    }
    int pop() {
        int val = heap.front();
        heap.front() = heap.back();
        heap.pop_back();
        int i = 0, n = heap.size();
        while (true) {
            int l = 2 * i + 1, r = l + 1, smallest = i;
            if (l < n && heap[l] < heap[smallest]) smallest = l;
            if (r < n && heap[r] < heap[smallest]) smallest = r;
            if (smallest == i) break;
            swap(heap[i], heap[smallest]);
            i = smallest;
        }
        return val;
    }
};
int main() {
    PriorityQueue pq;
    for (int value : {10, 5, 1}) pq.push(value);
    cout << "Heap array: [";
    for(size_t i = 0; i < pq.heap.size(); i++) {
        if (i) cout << ", ";
        cout << pq.heap[i];
    }
    cout << "]\n";
}

import java.util.*;
public class Main {
    static class PriorityQueue {
        List<Integer> heap = new ArrayList<>();
        void push(int val) {
            heap.add(val);
            int i = heap.size() - 1;
            while (i > 0) {
                int parent = (i - 1) / 2;
                if (heap.get(i) >= heap.get(parent)) break;
                Collections.swap(heap, i, parent);
                i = parent;
            }
        }
        int pop() {
            int val = heap.get(0);
            heap.set(0, heap.get(heap.size() - 1));
            heap.remove(heap.size() - 1);
            int i = 0, n = heap.size();
            while (true) {
                int l = 2 * i + 1, r = l + 1, smallest = i;
                if (l < n && heap.get(l) < heap.get(smallest)) smallest = l;
                if (r < n && heap.get(r) < heap.get(smallest)) smallest = r;
                if (smallest == i) break;
                Collections.swap(heap, i, smallest);
                i = smallest;
            }
            return val;
        }
    }
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue();
        for (int value : new int[]{10, 5, 1}) pq.push(value);
        System.out.println("Heap array: " + pq.heap);
    }
}

Watch it run

Step through it

Running on insert 10, then 5, then 1

Output

Read all 12 Steps

Empty heap A min-heap stored as a flat array. Children of index i live at 2i+1 and 2i+2 — no pointers needed.
Insert 10 The first value becomes the root at index 0.
Insert 5 New items are appended at the end, index 1, then sifted up.
Sift up 5 < its parent 10, so they swap. The smallest value must sit at the root.
Insert 1 Append 1 at index 2. Its parent is (2-1)//2 = 0, holding 5.
Sift up 1 < 5, so swap. 1 reaches the root after one comparison per level — O(log n).
Heap property Every parent is ≤ both children. Note the array is NOT sorted: [1, 10, 5]. Heap order is weaker than full sorting.
Peek The minimum is always at index 0, so peek costs O(1).
Extract min Remove 1. To keep the array dense, move the LAST element into the root rather than shifting everything.
Sift down 5's only child is 10. 5 ≤ 10, so it stays put and the heap is valid again.
Why sift-down differs Sift-up compares against one parent; sift-down must check both children to find the smaller. That is a constant factor, not a complexity change.
Building in bulk Inserting n items one by one is O(n log n). Heapifying an existing array bottom-up is O(n), because half the nodes are leaves that never move.

Where It Is Used, and the Library Forms

Dijkstra's algorithm is the standard application: repeatedly extract the unvisited vertex with the smallest tentative distance. The priority queue is what makes it efficient — a linear scan for that vertex would give O(V²). A\* search is the same loop with the priority being cost-so-far plus a heuristic estimate.

Merging k sorted lists puts the head of each list into a heap of size k, repeatedly extracting the smallest and pushing the next element from that list. The result is O(N log k) rather than the O(N·k) of repeated linear scans, and it is the basis of the merge phase of external sorting.

Top-k problems use a heap of fixed size k, which is the counterintuitive part: to find the k largest elements, keep a min heap of size k. Each new element is compared against the smallest kept; if larger, replace it. This is O(n log k) and O(k) space, better than sorting everything when k is small relative to n.

Scheduling is the operating-system case — a run queue ordered by process priority — and event simulation orders pending events by timestamp. Huffman coding repeatedly extracts the two least frequent symbols to build its tree.

The library forms differ in an important way. Python provides heapq, which operates on a plain list rather than wrapping it in a class, and is a min heap only — negate for a max heap. C++ provides std::priority_queue, which is a max heap by default, reversed with std::greater; the underlying make_heap, push_heap and pop_heap are also exposed for direct use on a container. Java provides PriorityQueue, a min heap by default, accepting a Comparator for any other ordering.

Note the default differs between C++ and the other two, which is a routine source of inverted results when porting code between them.

Dijkstra, A*, Huffman, scheduling and event simulation
Merge k sorted lists in O(N log k) with a heap of size k
For the k largest, keep a min heap of size k — O(n log k)
Python and Java default to min; C++ defaults to max