Heaps

Analogy categoryAnalogies

Introduction

A heap is a complete binary tree that satisfies the heap-order property: in a min-heap, every parent node's value is less than or equal to its children's values (so the minimum is always at the root); in a max-heap, every parent's value is greater than or equal to its children's values (so the maximum is always at the root). Because heaps are complete binary trees, they can be stored compactly in a plain array with no pointers, using index arithmetic to locate parent and child nodes. Heaps are the classic implementation behind priority queues and are the core mechanism of heap sort.

🏏

Cricket analogy: A heap is like a batting order where every parent slot must outscore the players below it in the tree, so the top run-scorer always sits at the root, and because the shape is a complete tree it can be listed in a simple scoresheet array with no need for player-linking notes.

Structure/Syntax

python

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

    def _parent(self, i):
        return (i - 1) // 2

    def _left(self, i):
        return 2 * i + 1

    def _right(self, i):
        return 2 * i + 2

    def push(self, value):
        self.data.append(value)
        self._sift_up(len(self.data) - 1)

    def _sift_up(self, i):
        while i > 0 and self.data[i] < self.data[self._parent(i)]:
            p = self._parent(i)
            self.data[i], self.data[p] = self.data[p], self.data[i]
            i = p

Explanation

For a node stored at index i in the array, its parent is at index (i-1)//2, its left child is at 2*i+1, and its right child is at 2*i+2 — this arithmetic works precisely because a heap is always a complete binary tree with no gaps. Inserting a new element (push) appends it to the end of the array and then 'sifts up' (bubbles up), repeatedly swapping it with its parent while it violates the heap property, until it settles into a valid position. Removing the minimum/maximum (pop) swaps the root with the last element, removes the last element (which was the old root), and then 'sifts down' (bubbles down) the new root by repeatedly swapping it with its smaller (min-heap) or larger (max-heap) child until the heap property is restored. Building a heap from an unsorted array of n elements can be done in O(n) time by calling sift-down on all non-leaf nodes from the last non-leaf up to the root (this is more efficient than n individual O(log n) insertions).

🏏

Cricket analogy: In the squad array, a player's captain sits at index (i-1)//2 and their two vice-captains at 2i+1 and 2i+2; adding a new recruit appends them at the end and 'sifts up' past weaker seniors, while dropping the top scorer swaps in the last player and 'sifts down' past stronger juniors until order is restored, and ranking the whole squad from scratch takes one O(n) pass from the bottom up.

Example

python

def _sift_down(data, i, n):
    while True:
        left, right, smallest = 2 * i + 1, 2 * i + 2, i
        if left < n and data[left] < data[smallest]:
            smallest = left
        if right < n and data[right] < data[smallest]:
            smallest = right
        if smallest == i:
            break
        data[i], data[smallest] = data[smallest], data[i]
        i = smallest

def pop_min(heap: MinHeap):
    data = heap.data
    root = data[0]
    last = data.pop()
    if data:
        data[0] = last
        _sift_down(data, 0, len(data))
    return root

heap = MinHeap()
for v in [5, 3, 8, 1, 9, 2]:
    heap.push(v)
print(heap.data)      # array-based heap layout
print(pop_min(heap))  # 1 (the minimum)
print(heap.data)      # heap after removing the minimum

Complexity

Push (insert) and pop (extract-min/max) each run in O(log n) time because sift-up and sift-down traverse at most the height of the tree, which is O(log n) for a complete binary tree with n nodes. Peeking at the min/max is O(1) since it's always the root, stored at index 0. Building a heap from n elements via bottom-up heapify runs in O(n) time overall (a tighter bound than the naive O(n log n) from n sequential insertions), which is why heap sort's build phase is O(n) even though the subsequent n extractions each cost O(log n), giving heap sort an overall O(n log n) time complexity.

🏏

Cricket analogy: Promoting or demoting a player in the squad ranking takes O(log n) because the sift only travels the height of the squad tree, while checking who's currently top-ranked is instant O(1) since they're always at the front of the scoresheet, and ranking a brand-new squad of n players from scratch is O(n) overall, not O(n log n).

Key Takeaways

A heap is a complete binary tree stored as an array, with parent/child found via index arithmetic.
Min-heap: parent <= children (min at root). Max-heap: parent >= children (max at root).
Insert uses sift-up; extract-min/max uses sift-down; both are O(log n).
Building a heap from n elements bottom-up is O(n), not O(n log n).
Heaps power priority queues and heap sort, which runs in O(n log n) overall.

Practice what you learned

1. In an array-based heap, what is the index of the left child of the node at index i?

2. What is always true about the root of a min-heap?

3. What is the time complexity of building a heap from n unsorted elements using bottom-up heapify?

4. What operation is used to restore the heap property after removing the root element?

Was this page helpful?

AVL Trees

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#Heaps#Structure#Syntax#Explanation#Example#StudyNotes#SkillVeris