SwadhyAI Notes

All DSA notes

DSA Priority Structures

Priority Queues & Binary Heaps

You need the next highest-scoring feed story as scores change. Sorting the whole pool after every update is correct; at n = 10⁶ updates it is not fast enough. You only need the current best, not a full order.

A is the ADT. A binary heap implements it by keeping a and a invariant, so peek is O(1) and insert/extract are O(log n).

Heap journey

1

Need the extremum

Repeated next-best access while the set changes.

2

Keep a complete tree so the array layout stays dense.

3

Every parent beats its children; siblings are unordered.

4

Sift up on insert; sift down on extract root.

What actually happens

Naive idea: keep an unsorted array and scan for the minimum on every extract (O(n)), or keep a fully sorted array and pay O(n) on every insert. Fine for tiny n; painful when both operations repeat.

Better idea: maintain only partial order. Append to preserve shape, then to restore . Height is ⌊log₂ n⌋, so each repair walks O(log n) edges. Building from scratch uses in O(n).

The improved design still fails when you treat level order as globally sorted, sift against the wrong child, mutate priorities in place without repair, or need membership/range queries (prefer a balanced BST or hash map).

Invariants (shape + heap order)

After every successful operation the tree is complete (shape), and every parent–child edge satisfies the chosen order (min or max). The root is therefore the unique extremum among stored items; siblings may appear in any order.

How to choose a heap

1. Do you repeatedly need the next best item? Yes → priority queue / binary heap. Need full sort once → sort. Need arbitrary keys or ranges → tree or hash.

2. Is k ≪ n? Keep a size-k heap for top-k instead of sorting all n.

3. Building from an array? Prefer bottom-up (O(n)) over n pushes (O(n log n)).

Quantitative check

log₂(10⁶) ≈ 20. A million inserts cost about twenty million comparisons of repair work in the worst case, versus Θ(n log n) ≈ 2×10⁷ comparisons to fully sort once, then cheap peeks. Extracting the minimum n times from a heap is heapsort: still Θ(n log n), but online extracts interleave with inserts without resorting.

01 · Shape

A complete binary tree

02 · Order

Every parent beats its children

03 · Payoff

O(1) peek, O(log n) updates

The heap repair lab

Insert 2, step through its upward path, then extract the minimum and watch the repair reverse direction.

Interactive min-heap

Watch one repair path at a time

The tree and array are the same structure. Insert sifts up; extract-min sifts down.

3
8
5
12
10
7
Array representationparent(i) = ⌊(i − 1) / 2⌋
3
0
8
1
5
2
12
3
10
4
7
5
Repair trace1 / 1

A valid min-heap

Try inserting a value or extracting the minimum, then step through the repair path.

compareswapsettled

Two invariants, one compact array

1. Shape invariant

The tree is complete: every level is full except perhaps the last, which fills left to right. There are no holes, so level order fits directly in an array without child pointers.

2. Order invariant

In a min-heap, parent ≤ child on every edge; reverse it for a max-heap. Siblings and cousins have no ordering guarantee, so a heap is not a sorted tree.

Parent of i

⌊(i − 1) / 2⌋

Left child

2i + 1

Right child

2i + 2

A complete tree with n nodes has height ⌊log₂ n⌋. That height, not the number of nodes: is why a repair costs O(log n).

Operations and their repair zones

OperationWorst caseReason
peek min / maxO(1)The extremum is always stored at the root.
insertO(log n)Append, then sift up along one ancestor path.
extract rootO(log n)Move the last leaf to the root, then sift down.
build heapO(n)Bottom-up heapify; most nodes are already near the leaves.
find arbitrary valueO(n)Heap order does not tell which branch contains an ordinary key.
delete known indexO(log n)Replace it with the last leaf, then repair in one direction.

Insert → sift up

  1. Append at the next open leaf to preserve shape.
  2. Compare with its parent.
  3. Swap while the parent-child order is wrong.

Extract root → sift down

  1. Save the root and move the final leaf into its place.
  2. For a min-heap, compare against the smaller child.
  3. Swap downward until both child edges are valid.

A min-heap from first principles

Library heaps are preferable in production, but implementing the two repair loops makes the invariants concrete.

Python

python
1class MinHeap:
2    def __init__(self):
3        self.a = []
4
5    def push(self, value):
6        self.a.append(value)             # preserve shape
7        child = len(self.a) - 1
8
9        while child > 0:                 # repair upward
10            parent = (child - 1) // 2
11            if self.a[parent] <= self.a[child]:
12                break
13            self.a[parent], self.a[child] = self.a[child], self.a[parent]
14            child = parent
15
16    def pop_min(self):
17        if not self.a:
18            raise IndexError("pop from empty heap")
19
20        minimum = self.a[0]
21        last = self.a.pop()
22        if not self.a:
23            return minimum
24
25        self.a[0] = last                 # preserve shape
26        parent = 0
27        while True:                      # repair downward
28            left = 2 * parent + 1
29            right = left + 1
30            if left >= len(self.a):
31                break
32
33            smaller = left
34            if right < len(self.a) and self.a[right] < self.a[left]:
35                smaller = right
36            if self.a[parent] <= self.a[smaller]:
37                break
38
39            self.a[parent], self.a[smaller] = self.a[smaller], self.a[parent]
40            parent = smaller
41
42        return minimum

Java

java
1import java.util.ArrayList;
2import java.util.List;
3import java.util.NoSuchElementException;
4
5final class MinHeap {
6    private final List<Integer> a = new ArrayList<>();
7
8    void push(int value) {
9        a.add(value);                     // preserve shape
10        int child = a.size() - 1;
11
12        while (child > 0) {               // repair upward
13            int parent = (child - 1) / 2;
14            if (a.get(parent) <= a.get(child)) break;
15            swap(parent, child);
16            child = parent;
17        }
18    }
19
20    int popMin() {
21        if (a.isEmpty()) throw new NoSuchElementException("pop from empty heap");
22
23        int minimum = a.get(0);
24        int last = a.remove(a.size() - 1);
25        if (a.isEmpty()) return minimum;
26
27        a.set(0, last);                    // preserve shape
28        int parent = 0;
29        while (true) {                     // repair downward
30            int left = 2 * parent + 1;
31            int right = left + 1;
32            if (left >= a.size()) break;
33
34            int smaller = left;
35            if (right < a.size() && a.get(right) < a.get(left)) {
36                smaller = right;
37            }
38            if (a.get(parent) <= a.get(smaller)) break;
39
40            swap(parent, smaller);
41            parent = smaller;
42        }
43
44        return minimum;
45    }
46
47    private void swap(int i, int j) {
48        int temporary = a.get(i);
49        a.set(i, a.get(j));
50        a.set(j, temporary);
51    }
52}

Why bottom-up heapify is O(n), not O(n log n)

Start at the last parent, index ⌊n/2⌋ − 1, and sift each parent down. About half the nodes are leaves and cost nothing; a quarter can move only one level; an eighth can move two. The weighted work isn/4 · 1 + n/8 · 2 + n/16 · 3 + … = O(n).

≈ n/2 nodes

height 0 · 0 work

≈ n/4 nodes

height 1 · ≤ 1 swap

≈ n/8 nodes

height 2 · ≤ 2 swaps

1 root

height log n · rare expensive node

Repeatedly calling push is O(n log n); Floyd’s bottom-up construction uses the uneven node heights and is O(n).

Patterns that reuse the heap

Streaming top k

O(n log k)

To keep the k largest items, use a size-k min-heap. The root is the weakest winner: replace it only when a larger value arrives.

Merge k sorted streams

O(N log k)

Put one current head from each stream in the heap. Pop the smallest, emit it, then push only its successor.

Best-first graph search

next cheapest state

Dijkstra and Prim prioritize the smallest frontier key. When decrease-key is unavailable, push the improved entry and skip stale entries when popped.

Running median

two heaps

A max-heap stores the lower half and a min-heap stores the upper half. Rebalance sizes; the roots meet at the median.

Scheduling & simulation

event time / priority

Store future events by timestamp or jobs by urgency. A monotonic counter can break ties while preserving arrival order.

Kth element

keep the opposite heap

Kth largest → min-heap of k. Kth smallest → max-heap of k. The root should be the candidate easiest to evict.

Choose the structure by the operation you repeat

StructureInsertPeek extremumExtract extremumBest reason to choose it
Unsorted arrayO(1)O(n)O(n)Fast writes; few priority reads
Sorted arrayO(n)O(1)O(1)*Iterate everything in order
Binary heapO(log n)O(1)O(log n)Repeated best-item access
Balanced BSTO(log n)O(log n)**O(log n)Ordered search and range queries

*When the extremum is stored at the removable end. **Can be O(1) with a cached pointer. A BST supports operations a heap does not, such as predecessor and range iteration.

Pitfalls worth remembering

  • Assuming an in-order or level-order traversal is globally sorted.
  • Sifting down against the wrong child; a min-heap must choose the smaller child.
  • Forgetting stale entries in Dijkstra when the library has no decrease-key.
  • Using mutable priorities after insertion: the heap will not repair itself.
  • Ignoring tie-breaking when tuple priorities contain non-comparable objects.

Simple rule of thumb

If the question repeatedly asks for the next smallest/largest item while data changes, think heap. If it asks for membership, arbitrary keys, or ranges, think hash table or balanced tree. If k ≪ n, keep only k candidates rather than sorting all n.

Compass: the root should be the item you need next, or the candidate you most want to evict.

Exercises

  1. Array [3, 1, 4, 1, 5] as a min-heap candidate. Which edges violate ? Show one sift that restores both shape and order after inserting 0 at the end.
  2. For n = 2²⁰, compare building with n pushes versus bottom-up . Which asymptotic label changes, and why are most nodes cheap?
  3. Design a size-k structure for the k largest of a stream. Why is the root of a min-heap of size k the right eviction candidate, and what breaks if you use a max-heap of size k instead?

Primary sources

  • Cormen et al., Introduction to Algorithms (CLRS): heapsort, priority queues, and build-heap analysis.
  • Williams, “Algorithm 232: Heapsort” (Communications of the ACM, 1964).
  • Python heapq and Java PriorityQueue documentation (binary heap contracts).

Takeaway

A binary heap is a complete tree with parent-beats-child order. Keep both invariants under every insert and extract, and you get O(1) peek with O(log n) updates without sorting the world.