Lesson 4 · Non-linear structures

Heaps and Priority Queues

A heap is a specialized tree-based data structure that satisfies the heap property: the parent node is always smaller (or larger) than its children. It guarantees O(1) access to the highest-priority element.

The Heap Property

A binary heap is a complete binary tree satisfying the heap property: in a min heap every node is less than or equal to its children, so the smallest value sits at the root; in a max heap every node is greater than or equal to its children, putting the largest at the root.

The property is deliberately local and this is the key insight. It constrains each node only against its own children — it says nothing about siblings, nothing about cousins, and nothing about nodes in different subtrees. A heap is therefore only partially ordered, unlike a binary search tree which is totally ordered.

That weakness is exactly what makes heaps fast. Maintaining a full ordering after every change is expensive; maintaining only the parent-child relation requires fixing a single path from root to leaf, which is O(log n). The heap gives up the ability to search in exchange for cheap access to one extreme value.

The consequence is worth stating plainly because it is the most common misunderstanding: finding the minimum in a max heap takes O(n), not O(log n). The smallest element could be any leaf, and there are n/2 of them. A heap answers one question quickly — what is the extreme — and everything else at linear cost.

Completeness is the second requirement: every level is filled except possibly the last, which is packed to the left with no gaps. This is not incidental. It bounds the height at exactly ⌊log₂ n⌋, and it is what permits the array representation below.

Min heap: parents ≤ children. Max heap: parents ≥ children
The property is local — siblings are entirely unordered
Partial ordering is why updates cost O(log n) rather than more
Searching for anything but the root is O(n)

Stored as an Array

A complete tree has no gaps, so its nodes can be laid out level by level in an array with no pointers at all. This is the representation every real heap implementation uses.

Reading the tree becomes arithmetic. For the node at index i, its left child is at 2i + 1, its right child at 2i + 2, and its parent at ⌊(i − 1) / 2⌋. The root is index 0. Some texts index from 1 instead, giving the cleaner 2i, 2i+1, and ⌊i/2⌋ — either is fine, but mixing them is a reliable source of off-by-one errors.

The benefits are substantial and often understated. Memory drops to the values alone, with none of the two-pointers-per-node overhead a linked tree carries. The elements sit contiguously, so traversal is cache-friendly where pointer chasing is not. And there is no allocation per node — a heap is one array that grows by doubling.

This is a large part of why heaps outperform their asymptotics. A binary search tree and a heap both do O(log n) work per operation, but the heap does it by walking indices in one contiguous block while the tree chases pointers across scattered memory.

The representation only works because the tree is complete. A sparse tree stored this way would leave the array full of unused gaps, and the index arithmetic would break down.

Children of index i are at 2i+1 and 2i+2; the parent is at ⌊(i−1)/2⌋
No pointers, no per-node allocation — just one array
Contiguous storage makes it far more cache-friendly than a linked tree
Only valid because a heap is always complete

Insertion and Extraction

Both operations work the same way: make the change in the only place that preserves completeness, then repair the heap property along a single path.

Insertion appends the new value at the end of the array — the only position that keeps the tree complete. That may violate the heap property against its parent, so the value sifts up: while it beats its parent, swap them and continue. The loop stops at the root or when the parent already beats it. Since it climbs one level per swap, this is O(log n).

Extraction removes the root, which is the whole point of the structure. But the root cannot simply be deleted — that would leave a hole. Instead, move the last element into the root, shrink the array by one, and let that value sift down: repeatedly compare it against its children, swap with the better of the two, and continue until both children are worse or it reaches a leaf.

The detail that catches people is that sift-down must compare against both children and swap with the stronger one. Swapping with the first child that beats it can promote the wrong value and leave the heap property violated — a bug that produces a structure that looks like a heap and gradually returns wrong answers.

Both operations touch exactly one root-to-leaf path, so both are O(log n). Reading the extreme without removing it — peek or top — is just reading index 0, at O(1).

Note that the two use opposite directions for a structural reason: an inserted value arrives at the bottom and can only be too good for its position, so it rises; a replacement value arrives at the top and can only be too poor, so it descends.

Heap operations and their costs
Operation	How	Cost
`peek`	Read index 0	O(1)
`insert`	Append, then sift up	O(log n)
`extract`	Move last to root, sift down	O(log n)
`build` from an array	Sift down from the last internal node	O(n)
Search for an arbitrary value	Scan	O(n)
`decrease-key`	Change, then sift up	O(log n), needs the index

Insert appends and sifts up; extract replaces the root and sifts down
Sift-down must compare both children and take the better
Both cost O(log n) — one root-to-leaf path
peek is O(1), a plain read of index 0

Key reference

Terms, operations, and practical uses

Core vocabulary

Complete Binary TreeA tree where every level is fully populated except possibly the last, which is filled left-to-right.
Heap PropertyThe structural invariant that every parent node is less than or equal to (or greater than or equal to) its children. Equal values are allowed — a heap is not strictly ordered.
Priority QueueAn abstract data type where elements are dequeued according to their priority, not their arrival time.

Operations

Sift-UpMoving a newly inserted element up the tree by swapping with its parent until the heap property is restored.
Sift-DownMoving a new root element down the tree by swapping with its highest-priority child.
HeapifyAn O(N) algorithm for organizing an unsorted array into a valid heap by sifting down nodes from bottom to top.

Practical uses

Dijkstra's AlgorithmUsing a min-heap to efficiently find the shortest path in a weighted graph.
Top K ElementsMaintaining a min-heap of size K to find the K largest items in a massive stream of data without sorting.
Median MaintenanceUsing two balanced heaps (one min, one max) to constantly track the median of a dynamic dataset.

Implementation

Insert 3 into a Min-Heap

def insert(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] < heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break
heap = [5, 8, 12]
insert(heap, 3)
print(heap)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void insert(vector<int>& heap, int val) {
    heap.push_back(val);
    int i = heap.size() - 1;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] < heap[parent]) {
            swap(heap[i], heap[parent]);
            i = parent;
        } else break;
    }
}
int main() {
    vector<int> heap = {5, 8, 12};
    insert(heap, 3);
    cout << '[';
    for (size_t i = 0; i < heap.size(); i++) {
        if (i) cout << ", ";
        cout << heap[i];
    }
    cout << "]\n";
}

import java.util.*;
public class Main {
    static void insert(ArrayList<Integer> heap, 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)) {
                int temp = heap.get(i);
                heap.set(i, heap.get(parent));
                heap.set(parent, temp);
                i = parent;
            } else break;
        }
    }
    public static void main(String[] args) {
        ArrayList<Integer> heap = new ArrayList<>(Arrays.asList(5, 8, 12));
        insert(heap, 3);
        System.out.println(heap);
    }
}

Watch it run

Step through it

Running on heap = [5, 8, 12], insert 3

Output

Read all 7 Steps

Initial Min-Heap Root 5 with children 8 and 12. Flat array: [5, 8, 12].
Append 3 The new value lands at the end of the array — index 3, the left child of 8.
Compare with parent Index 3's parent is (3 - 1) // 2 = 1. Compare 3 against 8.
Swap 3 and 8 3 is smaller than 8, so they swap. 3 climbs one level.
Compare with new parent 3 now sits at index 1. Its parent is (1 - 1) // 2 = 0. Compare 3 against 5.
Swap 3 and 5 3 is smaller than 5, so they swap again and 3 reaches the root.
Restored Min-Heap 3 is at the root and every parent is ≤ its children. Flat array: [3, 5, 12, 8].

Building in Linear Time

Converting an existing unordered array into a heap looks like it should cost O(n log n) — insert each of n elements at O(log n) each. Floyd's build-heap algorithm does it in O(n), and the reason is a genuinely useful piece of analysis.

The method is to sift down from the last internal node backwards to the root, at index ⌊n/2⌋ − 1 down to 0. Every node from ⌊n/2⌋ onwards is a leaf and is already a valid one-element heap, so half the array needs no work at all.

The cost argument turns on where the nodes are. Sift-down costs proportional to the node's height, and in a complete tree most nodes are near the bottom where the height is small. There are n/2 nodes at height 0 costing nothing, n/4 at height 1 costing one step, n/8 at height 2 costing two, and so on. The sum ∑ (n / 2^(h+1)) · h converges to 2n, giving O(n).

The contrast with the naive approach is instructive: repeated insertion sifts up, and the expensive nodes there are the numerous leaves, each potentially climbing the full height. Sifting down makes the cheap operations the common ones — the same total structure, analysed from the other end.

This linear build is what makes heap sort work: build the heap in O(n), then extract the maximum n times at O(log n) each, giving O(n log n) overall with O(1) extra space since the sorted output fills the array from the back as the heap shrinks. Heap sort is not stable and has poorer cache behaviour than quicksort, which is why it is usually a fallback — notably in introsort, which switches to it when quicksort's recursion runs too deep.

Two practical notes. Most libraries provide only a min heap — Python's heapq, Java's PriorityQueue — so a max heap is obtained by negating values or supplying a reversed comparator. And decrease-key, needed by Dijkstra's algorithm, requires knowing where an element currently sits; since heaps offer no lookup, implementations either maintain a position map or, more commonly, push a duplicate entry and discard stale ones on extraction.

Sift down from ⌊n/2⌋−1 to 0 — leaves are already valid heaps
Cost is bounded by ∑ n·h/2^(h+1), which converges to 2n
Heap sort: build in O(n), extract n times, O(1) extra space
Most libraries give a min heap — negate values for a max heap