Binary HeapBinary heaps

01Why it exists

Reach for it when you see:Pulling out the largest or smallest at any moment, priorities, whatever is due first, top-K, data that keeps arriving while you keep taking extremes out.

02The core idea

A heap is a complete binary tree: every level is filled before the next one begins, and each level fills from left to right. That shape is what lets it be stored directly in an array, with no pointers at all — the parent of index i sits at (i − 1) / 2, and its two children at 2i + 1 and 2i + 2.

The one rule is the heap property: in a min-heap every parent is no larger than its children (a max-heap is the other way round). Note that this constrains only parent and child. Siblings have no order between them, and neither do separate subtrees. A heap is therefore not sorted; all it guarantees is that the root is the minimum. Everything it declines to do is exactly why it is faster than sorting.

Both basic operations work by breaking the rule and then repairing it. push: put the new element at the end of the array, the last position in the tree, then compare it with its parent and swap whenever it is smaller, floating it upwards (sift up). pop: take the root away, move the last element into the root, then compare it with the smaller of its two children and swap whenever it is larger, sinking it downwards (sift down). Neither travels further than the height of the tree, log n levels, so both are O(log n).

Building a heap out of n elements has a faster method: start at the last non-leaf node, work backwards, and sift each node down once. It looks like n rounds of log n, but the nodes near the bottom are the numerous ones and they have almost no distance to sink, and the sum works out to O(n). Python's heapify and C++'s make_heap both do it this way.

03The algorithm

1. 1push(x): append x to the end of the array and let i be its index.
2. 2While i is not the root and a[i] < a[parent]: swap the two and move i up to the parent. Otherwise stop.
3. 3pop(): save a[0] as the return value, move the last element into a[0], shorten the array by one, and set i = 0.
4. 4Find c, the smaller of i's two children. If a[c] < a[i]: swap them, move i to c and repeat; otherwise stop.
5. 5For a max-heap, reverse the direction of the comparisons — or negate the values and push them into a min-heap, the way Python does.

04Interactive demo

A fixed script of operations. The tree view is on top and the array view of the very same data is on the right; the two are one and the same thing. Amber marks the pair of nodes being compared, blue the pair that was just swapped.

05Code

Write one by hand to get sift up and sift down straight, then reach for heapq or std::priority_queue in practice. Note that Python gives you only a min-heap, while C++ defaults to a max-heap.

class MinHeap:
    """A min-heap stored in an array. The parent of index i is (i-1)//2, its children 2i+1 and 2i+2."""

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

    def push(self, x):
        self.a.append(x)                 # append first, keeping the complete-tree shape
        self._sift_up(len(self.a) - 1)   # then float it up to where it belongs

    def pop(self):
        top = self.a[0]                  # the minimum is always at the root
        last = self.a.pop()
        if self.a:
            self.a[0] = last             # move the last element to the root, then sink it
            self._sift_down(0)
        return top

    def peek(self):
        return self.a[0]

    def _sift_up(self, i):
        while i > 0:
            p = (i - 1) // 2
            if self.a[i] < self.a[p]:
                self.a[i], self.a[p] = self.a[p], self.a[i]
                i = p
            else:
                break

    def _sift_down(self, i):
        n = len(self.a)
        while True:
            l, r, smallest = 2 * i + 1, 2 * i + 2, i
            if l < n and self.a[l] < self.a[smallest]:
                smallest = l
            if r < n and self.a[r] < self.a[smallest]:
                smallest = r
            if smallest == i:
                break
            self.a[i], self.a[smallest] = self.a[smallest], self.a[i]
            i = smallest


# In practice, reach for the standard library: heapq is a min-heap
import heapq

h = []
heapq.heappush(h, 7)
heapq.heappush(h, 3)
heapq.heappush(h, 9)
print(heapq.heappop(h))      # 3

# For a max-heap, negate the values
big = []
heapq.heappush(big, -7)
heapq.heappush(big, -9)
print(-heapq.heappop(big))   # 9

# Building from an existing list is O(n), faster than pushing one at a time at O(n log n)
nums = [7, 3, 9, 1, 4, 8]
heapq.heapify(nums)
print(nums[0])               # 1

06Practice

• LeetCode 1046Last Stone Weight (a max-heap)Easy
• LeetCode 703Kth Largest Element in a StreamEasy
• LeetCode 23Merge k Sorted Lists (the heap holds the k list heads)Hard
• LeetCode 621Task SchedulerMedium
• LeetCode 1942The Number of the Smallest Unoccupied Chair (two heaps acting as timers)Medium