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.

What is a Heap?

A Heap is a complete binary tree that maintains a specific ordering. In a Min-Heap, every parent node is smaller than or equal to its children, making the root the smallest element.

A Max-Heap operates the exact same way but reversed: every parent is larger than its children, putting the largest element at the root.

A complete binary tree structure
Min-Heap: root is the minimum element
Max-Heap: root is the maximum element

Why it is useful

Heaps are the standard way to implement a Priority Queue. Unlike a standard queue (FIFO), a priority queue always serves the most urgent item first, regardless of when it arrived.

This is essential for algorithms like Dijkstra's shortest path, A* search, and scheduling tasks in operating systems.

Implements Priority Queues efficiently
Constant O(1) time to find the min/max
Logarithmic O(log N) time to insert or remove

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.

Code example

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)

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;
    }
}

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;
    }
}

Inputheap = [5, 8, 12], insert 3

Output[3, 5, 12, 8]

Example

Run the example step by step

Output

Array Representation

Because a heap is a complete binary tree (filled left to right), it can be perfectly flattened into a 1D array without needing pointer objects.

For any node at index i, its left child is at (2i + 1), its right child is at (2i + 2), and its parent is at floor((i - 1) / 2). This array math makes heaps incredibly memory-efficient.

Stored contiguously in an array
No node pointers needed
Child math: left = 2i+1, right = 2i+2

Insertion (Sift-Up)

When inserting a new value, it is placed at the very end of the array to maintain the complete tree shape. Then, it 'sifts up' (or bubbles up).

The new node compares itself to its parent. If it violates the heap property (e.g. it is smaller than its parent in a Min-Heap), they swap. This continues until it reaches a valid position.

Add to the end of the array
Compare with parent and swap if needed
Maximum swaps equals the tree height (O(log N))

Deletion (Sift-Down)

A priority-queue interface normally removes the root element (the minimum or maximum). A heap can remove a known arbitrary index too, but locating an arbitrary value is O(N) unless another index is maintained. For root removal, move the last array element to the root.

This new root then 'sifts down' by swapping with its smallest child (in a Min-Heap) until the heap property is restored.

Remove the root and replace it with the last leaf
Compare with children and swap with the smaller one
Continues down the tree in O(log N) time

Time and space costs

Accessing the top element is O(1). Inserting a new element or extracting the top element takes O(log N) time. Building a heap from an unsorted array takes O(N) time using the 'heapify' algorithm.

The space complexity is O(N) to store the elements, with O(1) auxiliary space since the tree is mapped directly onto a flat array.

Access min/max: O(1)
Insert/Delete: O(log N)
Heapify an array: O(N) time

Common mistakes

A common mistake is assuming that a heap is fully sorted. It is not; the only guarantee is the vertical parent-child relationship. Siblings have no guaranteed order.

Another pitfall is trying to search for an arbitrary element inside a heap. Since it's not fully sorted like a BST, searching takes O(N) time.

Heaps are not fully sorted arrays
Searching for a random value is slow (O(N))
Siblings have no guaranteed relative order