GeeksforGeeks Medium

Implement Max Heap

Build a max-heap from scratch: push, pop-max, and heapify on a plain array.

heapdesign

02

Intuition

💡

A heap is a complete binary tree flattened into an array: children of i live at 2i+1 and 2i+2. Only one rule — parent ≥ children. Push bubbles a new leaf up; pop moves the last leaf to the root and sifts it down. Everything is swaps along one root-to-leaf path.

03

Approach

1

Array as tree

Completeness means no gaps: parent(i) = (i−1)//2. No pointers, great cache behaviour.

2

sift-up on push

Append at the end; swap with the parent while bigger than it. At most log n swaps.

3

sift-down on pop

Replace root with the last element; repeatedly swap with the larger child while smaller than it. Build-heap runs sift-down from n//2−1 backwards — O(n) total.

04

Solution & live demo

python

▶1class MaxHeap:
▶2    def __init__(self): self.a = []
▶3 
▶4    def push(self, x):
▶5        a = self.a; a.append(x); i = len(a) - 1
▶6        while i and a[(i - 1) // 2] < a[i]:
▶7            a[(i - 1) // 2], a[i] = a[i], a[(i - 1) // 2]
▶8            i = (i - 1) // 2
▶9 
▶10    def pop(self):
▶11        a = self.a
▶12        top, last = a[0], a.pop()
▶13        if a:
▶14            a[0] = last
▶15            i, n = 0, len(a)
▶16            while True:
▶17                l, r, big = 2*i + 1, 2*i + 2, i
▶18                if l < n and a[l] > a[big]: big = l
▶19                if r < n and a[r] > a[big]: big = r
▶20                if big == i: break
▶21                a[i], a[big] = a[big], a[i]
▶22                i = big
▶23        return top

05

Edge cases

Pop from size-1 heap

Root is the last element — remove and return, no sift.

Equal keys

≥ comparisons make ties stable enough; heap order tolerates equals on either side.

06

Complexity

Time

O(log n) per op

Space

O(1) extra

Build-heap from raw array is O(n).