Data Structure

Max Heap

“The VIP Club”

Search: O(n)

Space: O(n)

Self-Balancing: No

History

The Heap was introduced by J.W.J. Williams in 1964 as a data structure specifically designed for the Heapsort algorithm.

It is a "Priority Queue" implementation. It doesn't care about sorting everything perfectly; it only cares that the most important element (the max) is accessible instantly. It's the bouncer at the club who only lets the biggest celebrity stand at the front.

Core Property

The Heap Property

For any given node $I$ , the value of $I$ is greater than or equal to the values of its children. This means the largest element is always at the Root.

How It Works

Heaps are usually implemented as Arrays, not node objects. We use math to simulate the tree structure.

Parent index: $\lfloor (i-1)/2 \rfloor$
Left Child: $2i + 1$
Right Child: $2i + 2$

The Operations

Insert (Bubble Up): Add to the end of the array, then swap with parent until the property is restored.
Extract Max (Bubble Down): Take the root (max), move the last element to the root, then swap it down with the larger child until it settles.

SearchO(n)

Heaps are not for searching. Finding an arbitrary element requires scanning the array.

InsertO(log n)

We add to the bottom and swim up. The height is always $log n$.

DeleteO(log n)

Specifically for deleting the Root (Extract Max). Deleting an arbitrary node is harder.

SpaceO(n)

Extremely efficient. It's just a raw array with zero pointer overhead.

Code Walkthrough

Complete data structure implementations in multiple programming languages. Select a language to view idiomatic code.

1class MaxHeap:
2    """Array-based Max Heap implementation.
3
4    Parent index:      (i - 1) // 2
5    Left child index:  2 * i + 1
6    Right child index: 2 * i + 2
7    """
8    def __init__(self):
9        self.heap: list[int] = []
10
11    def _parent(self, i: int) -> int:
12        return (i - 1) // 2
13
14    def _left_child(self, i: int) -> int:
15        return 2 * i + 1
16
17    def _right_child(self, i: int) -> int:
18        return 2 * i + 2
19
20    def _swap(self, i: int, j: int) -> None:
21        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
22
23    def insert(self, val: int) -> None:
24        """Insert value and bubble up to maintain heap property."""
25        self.heap.append(val)
26        self._bubble_up(len(self.heap) - 1)
27
28    def _bubble_up(self, i: int) -> None:
29        """Move element up until heap property is satisfied."""
30        while i > 0:
31            parent = self._parent(i)
32            if self.heap[i] <= self.heap[parent]:
33                break
34            self._swap(i, parent)
35            i = parent
36
37    def extract_max(self) -> int | None:
38        """Remove and return the maximum element."""
39        if not self.heap:
40            return None
41
42        max_val = self.heap[0]
43        last = self.heap.pop()
44
45        if self.heap:
46            self.heap[0] = last
47            self._sink_down(0)
48
49        return max_val
50
51    def _sink_down(self, i: int) -> None:
52        """Move element down until heap property is satisfied."""
53        n = len(self.heap)
54        while True:
55            largest = i
56            left = self._left_child(i)
57            right = self._right_child(i)
58
59            if left < n and self.heap[left] > self.heap[largest]:
60                largest = left
61            if right < n and self.heap[right] > self.heap[largest]:
62                largest = right
63
64            if largest == i:
65                break
66
67            self._swap(i, largest)
68            i = largest
69
70    def peek(self) -> int | None:
71        """Return the maximum element without removing it."""
72        return self.heap[0] if self.heap else None