Know this before you start: “Push and pop in O(log n)”

Why heap push and pop are O(log n)

A new item bubbles up and a removed top is replaced and sifts down, each along one path of a balanced tree: about log₂ n steps.

The idea

The heap's array is a complete binary tree: item i's children are at 2i + 1 and 2i + 2. Its height is about log₂ n.

Push puts the item at the end and swaps it up while it's smaller than its parent. Pop moves the last item to the top and swaps it down with its smaller child until the rule holds again. Each walks one root-to-leaf path, so O(log n).

See it step by step

Push 2 into the heap [3, 5, 8]

Place 2 at the end: [3, 5, 8, 2]. Its parent (index 1) is 5.
2 < 5 → swap: [3, 2, 8, 5]. Parent now 3.
2 < 3 → swap: [2, 3, 8, 5]. At the top: done after 2 swaps.

In code (Python)

def push(heap, x):
    heap.append(x)
    i = len(heap) - 1
    while i > 0 and heap[(i - 1) // 2] > heap[i]:      # smaller than its parent
        parent = (i - 1) // 2
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent

def pop(heap):
    top = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        i = 0
        while True:
            smallest = i
            for child in (2 * i + 1, 2 * i + 2):
                if child < len(heap) and heap[child] < heap[smallest]:
                    smallest = child
            if smallest == i:
                break
            heap[i], heap[smallest] = heap[smallest], heap[i]
            i = smallest
    return top

h = []
for x in [3, 5, 8, 2]:
    push(h, x)
print(h)                   # [2, 3, 8, 5]
print(pop(h), pop(h))      # 2 3

Push: O(log n). Pop: O(log n). Peek: O(1).

When you'll use it

Understanding why heap solutions are O(n log n) or O(n log k), and explaining it in interviews.

Common mistakes

Calling a heap solution O(n) when it does n pushes (that's O(n log n)).
Mixing up child indexes (2i + 1, 2i + 2) with parent ((i − 1) // 2).