A sorted list gives the minimum in O(1) but an insert costs O(n). An unsorted list inserts in O(1) and finds the minimum in O(n). A heap is the middle way: inserting and removing the minimum take O(log n), peeking at the minimum is O(1). This is the structure behind a priority queue and heap sort.

A min-heap of seven elements as a tree and as an array
A min-heap of seven elements as a tree and as an array

What a heap is

  • A min-heap: every node is less than or equal to its children, so the root is the minimum. In a max-heap it is the opposite.
  • It is a complete binary tree: all levels are full except possibly the last, which fills from left to right.
  • A heap is not fully sorted: only the parent-child relation is kept, siblings are in no order.

Completeness lets us store the tree in an array without pointers. For a 0-based index i: the parent is (i - 1) // 2, the children are 2i + 1 and 2i + 2.

python
heap = [1, 3, 2, 7, 4, 5, 6]

def is_min_heap(a):
    return all(a[(i - 1) // 2] <= a[i] for i in range(1, len(a)))

i = 1
print("node", heap[i], "parent", heap[(i - 1) // 2])
print("children", heap[2 * i + 1], heap[2 * i + 2])
print(is_min_heap(heap), is_min_heap([3, 1, 2]))
text
node 3 parent 1
children 7 4
True False

push and pop

push appends the item at the end and sifts it up: while it is smaller than its parent, swap them. pop takes the root, puts the last item in its place and sifts it down: swap it with the smaller child until the order is restored. Both walk along one branch, so they take O(log n).

pop: the last element takes the root and sinks by swapping with the smaller child
pop: the last element takes the root and sinks by swapping with the smaller child