juniorHeaps and Maps

What is a binary heap and how does it maintain its order?

Updated Feb 20, 2026

Short answer

A binary heap is a complete binary tree satisfying the heap property: in a min-heap every parent is less than or equal to its children, so the minimum sits at the root. It maintains that property with sift-up after insertion and sift-down after removal, each O(log n) because the tree's height is logarithmic. Being complete, it is stored in a flat array with no pointers.

Deep explanation

Two invariants define it, and both matter:

  • Complete — every level is full except possibly the last, which fills left to right. This is what allows array storage: for index i, children are at 2i+1 and 2i+2, and the parent at (i-1)//2.
  • Heap property — every parent compares favourably to its children. Note this is a partial order: it says nothing about siblings, so a heap is not sorted.
Python
def sift_up(heap, i):           # after appending at the end
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:
            break
        heap[parent], heap[i] = heap[i], heap[parent]
        i = parent


def sift_down(heap, i):         # after moving the last element to the root
    n = len(heap)
    while True:
        smallest, l, r = i, 2*i + 1, 2*i + 2
        if l < n and heap[l] < heap[smallest]: smallest = l
        if r < n and heap[r] < heap[smallest]: smallest = r
        if smallest == i: return
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

Insert appends at the end and sifts up — O(log n). Extract-min takes the root, moves the last element into its place, and sifts down — O(log n). Peek is O(1), just heap[0].

Building a heap from an existing array is the counter-intuitive part: sifting down from the midpoint backwards is O(n), not O(n log n), because most nodes are near the bottom and sift down only a short distance.

Real-world example

A scheduler always running the highest-priority job:

Python
import heapq
jobs = []
heapq.heappush(jobs, (3, 'send report'))
heapq.heappush(jobs, (1, 'page on-call'))
heapq.heappush(jobs, (2, 'rebuild index'))


heapq.heappop(jobs)   # (1, 'page on-call') — O(log n)

A sorted list would give O(1) access to the front but O(n) insertion as jobs arrive continuously. The heap costs O(log n) for both, which wins when insertions and removals are interleaved — exactly the scheduler's workload.

Common mistakes

  • - Assuming a heap is sorted. It guarantees only the root
  • printing the underlying array yields no meaningful order.
  • - Claiming heap construction from an array is O(n log n) — sifting down bottom-up is O(n).
  • - Using a heap to search for an arbitrary element, which is O(n) since the structure gives no guidance about where a value sits.
  • - Forgetting Python's `heapq` is a min-heap only
  • a max-heap needs negated keys or a custom wrapper.
  • - Breaking completeness by deleting from the middle without restoring the shape, which invalidates the array index arithmetic.

Follow-up questions

  • Why is building a heap from an array O(n) rather than O(n log n)?
  • How would you implement a max-heap with a min-heap library?
  • What is the difference between a binary heap and a binary search tree?
  • How do you decrease a key in a heap?

More Heaps and Maps interview questions

View all →