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

Source: https://skills101.in/learn/dsa/dsa-heaps-heap-sort-internals — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-18.

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 i | Index |
|---|---|
| left child | 2i + 1 |
| right child | 2i + 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](https://skills101.in/learn-img/dsa/heap-array.svg)

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).

```python
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)])
```

```text
[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](https://skills101.in/learn-img/dsa/heapify-steps.svg)

**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.

```python
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]))
```

```text
max-heap: [9, 4, 8, 1, 3, 7, 2]
[1, 2, 3, 4, 7, 8, 9]
```

| | Heap sort | Merge sort | Quick sort |
|---|---|---|---|
| Worst-case time | O(n log n) | O(n log n) | O(n²) |
| Extra space | O(1) | O(n) | O(log n) stack |
| Stable? | no | yes | no |

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.

```python
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))
```

```text
[95, 92, 88]
[95, 92, 88] [45, 60]
```

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

```java
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());
    }
}
```

```text
[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 quiz and free certificate: https://skills101.in/learn/dsa/dsa-heaps-heap-sort-internals