Skills101

AdvancedData Structures & Algorithms · Lesson 28 of 29 · Updated ·

Heaps and Heap Sort Internals — Array Layout, Sift Up, Heapify and Top-K

An earlier lesson used heaps as a ready-made tool (heapq, PriorityQueue) for top-k and running-median problems. Interviews also ask what happens inside: "implement a min-heap", "why is heapify O(n)?", "is heap sort stable?". This lesson opens the box.

1. A heap is a tree stored in an array

A binary min-heap is a complete binary tree (every level is full except maybe the last, which fills from the left) where every parent is ≤ its children. So the smallest value is always at the root. A max-heap is the same with ≥.

Because the tree is complete, it fits in a plain array with no gaps and no pointers:

For the node at index iIndex
left child2i + 1
right child2i + 2
parent(i − 1) // 2

A min-heap drawn as a tree with root 1, children 3 and 2, and leaves 4 9 8 7, and the same values stored in the array 1 3 2 4 9 8 7 at indexes 0 to 6

A heap is not sorted. In the picture, 3 is at index 1 and 2 is at index 2. The only promise is "parent ≤ children", which is enough to keep the minimum on top.

2. Sift up (push) and sift down (pop)

  • Push: put the new value at the end of the array, then sift up — swap it with its parent while it is smaller than the parent.
  • Pop: the answer is a[0]. Move the last value to index 0, shrink the array, then sift down — swap it with its smaller child while it is bigger than that child.

Both walk one root-to-leaf path, so both cost O(log n). Reading the minimum is O(1).

class MinHeap:
    def __init__(self):
        self.a = []

    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[(i - 1) // 2] > a[i]:          # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p

    def pop(self):
        a = self.a
        top = a[0]
        last = a.pop()
        if a:
            a[0] = last
            i, n = 0, len(a)
            while True:                                    # sift down
                small, l, r = i, 2 * i + 1, 2 * i + 2
                if l < n and a[l] < a[small]: small = l
                if r < n and a[r] < a[small]: small = r
                if small == i:
                    break
                a[i], a[small] = a[small], a[i]
                i = small
        return top

h = MinHeap()
for x in [9, 4, 7, 1, 3, 8, 2]:
    h.push(x)
print(h.a)
print([h.pop() for _ in range(7)])
[1, 3, 2, 9, 4, 8, 7]
[1, 2, 3, 4, 7, 8, 9]

3. Heapify: building a heap in O(n)

Pushing n values one by one costs O(n log n). There is a faster way to turn an existing array into a heap: sift down every parent, starting from the last parent (index n // 2 − 1) and moving back to the root. Leaves (the second half of the array) are already tiny heaps, so they are skipped.

Heapify of 9 4 7 1 3 8 2: sift down index 2 swaps 7 and 2, index 1 swaps 4 and 1, index 0 moves 9 down twice, giving 1 3 2 4 9 8 7

Why O(n), not O(n log n)? Half of the nodes are leaves and do no work. A quarter can sink 1 level, an eighth can sink 2 levels, and so on. The sum n/4·1 + n/8·2 + n/16·3 + … is less than n. Only the few nodes near the top can sink far. Python's heapq.heapify uses this method, which is why it is O(n).

4. Heap sort

Heap sort uses a max-heap inside the array itself:

  1. Heapify the array into a max-heap (O(n)).
  2. Swap the root (the maximum) with the last element of the heap part. The maximum is now in its final place.
  3. Shrink the heap by one and sift the new root down. Repeat until the heap has one element.
def sift_down(a, i, n):              # max-heap version
    while True:
        big, l, r = i, 2 * i + 1, 2 * i + 2
        if l < n and a[l] > a[big]: big = l
        if r < n and a[r] > a[big]: big = r
        if big == i:
            return
        a[i], a[big] = a[big], a[i]
        i = big

def heap_sort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)
    print("max-heap:", a)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)
    return a

print(heap_sort([9, 4, 7, 1, 3, 8, 2]))
max-heap: [9, 4, 8, 1, 3, 7, 2]
[1, 2, 3, 4, 7, 8, 9]
Heap sortMerge sortQuick sort
Worst-case timeO(n log n)O(n log n)O(n²)
Extra spaceO(1)O(n)O(log n) stack
Stable?noyesno

Heap sort's guarantee is its strength. In practice it is often slower than quick sort, because it jumps around the array and uses the CPU cache poorly.

5. Top-k with library heaps

To find the k largest of n numbers, keep a min-heap of size k. Its root is the smallest of the "current top k"; any new number bigger than the root replaces it. Cost: O(n log k), and only O(k) memory, which works even on a stream of data.

import heapq

def top_k(nums, k):
    h = []
    for x in nums:
        if len(h) < k:
            heapq.heappush(h, x)
        elif x > h[0]:
            heapq.heapreplace(h, x)      # pop the smallest, push x
    return sorted(h, reverse=True)

marks = [67, 92, 45, 88, 71, 95, 60, 83]
print(top_k(marks, 3))
print(heapq.nlargest(3, marks), heapq.nsmallest(2, marks))
[95, 92, 88]
[95, 92, 88] [45, 60]

In Java, PriorityQueue is a min-heap by default. Pass Collections.reverseOrder() for a max-heap.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] marks = {67, 92, 45, 88, 71, 95, 60, 83};
        int k = 3;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int x : marks) {
            minHeap.offer(x);
            if (minHeap.size() > k) minHeap.poll();   // drop the smallest
        }
        List<Integer> top = new ArrayList<>(minHeap);
        top.sort(Collections.reverseOrder());
        System.out.println(top);

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int x : marks) maxHeap.offer(x);
        System.out.println(maxHeap.poll() + " " + maxHeap.peek());
    }
}
[95, 92, 88]
95 92

Python's heapq has no max-heap; the usual trick is to push negated values (-x) and negate again when popping.

Common mistakes

  • Thinking a heap array is sorted. Only the root is guaranteed; printing a PriorityQueue shows the heap order, not sorted order.
  • In sift down, swapping with the first child that is smaller instead of the smaller of the two children; this breaks the heap rule.
  • Starting heapify at index 0 and going forward. Go from the last parent backwards to the root.
  • Using a max-heap of all n elements for top-k (O(n) memory) when a min-heap of size k is enough.
  • Calling heap sort stable. Equal values can change order.

Quick recap

  • A binary heap is a complete tree in an array: children at 2i+1 and 2i+2, parent at (i−1)//2.
  • Push = append + sift up; pop = move last to root + sift down; both O(log n).
  • Heapify by sifting down from the last parent to the root: O(n).
  • Heap sort: max-heapify, then swap root to the end and shrink; O(n log n), O(1) space, not stable.
  • Top-k largest: min-heap of size k, O(n log k).

Practice what you learned

📝 Quiz: Heaps and Heap Sort Internals5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →