Heap

How it Works

A heap is a complete binary tree stored efficiently in an array. "Complete" means every level is fully filled except possibly the last, which is filled from left to right. This property guarantees the tree is balanced and allows a compact array representation with no wasted space.

Heap Property: In a max-heap, the value of each node is greater than or equal to the values of its children. This ensures the maximum element is always at the root (index 0). A min-heap is the reverse — each parent is less than or equal to its children, putting the minimum at the root.

Array Representation: Because the tree is complete, we can map nodes to array indices without any pointers:

The root is at index 0.
For a node at index i:
- Left child is at index 2i + 1
- Right child is at index 2i + 2
- Parent is at index floor((i - 1) / 2)

Key Operations:

Insert: Add the new element at the end of the array (next available position in the tree), then bubble up (swap with parent) until the heap property is restored. Takes O(log n).
Extract-Max: The root holds the maximum. Swap it with the last element, remove the last element, then sink down (swap with the larger child) until the heap property is restored. Takes O(log n).
Heapify (Build Heap): Convert an arbitrary array into a valid max-heap by calling sink-down on every non-leaf node, starting from the last non-leaf and working up to the root. Despite appearances, this runs in O(n) time, not O(n log n).

Interactive Visualization

The tree view (top) shows the heap as a binary tree, while the array view (bottom) shows the same data in its underlying array form. Corresponding nodes and cells are highlighted together: red for active/swapping, yellow for parent being compared, and green for completed placement.

Use the controls below to perform heap operations.

def insert(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0:
        p = (i - 1) // 2
        if heap[i] > heap[p]:
            heap[i], heap[p] = heap[p], heap[i]
            i = p
        else: break
def extract_max(heap):
    max_val = heap[0]
    heap[0] = heap.pop()
    heapify_down(heap, 0)
    return max_val
def heapify_down(heap, i):
    n = len(heap)
    while True:
        largest = i
        l, r = 2*i+1, 2*i+2
        if l < n and heap[l] > heap[largest]: largest = l
        if r < n and heap[r] > heap[largest]: largest = r
        if largest == i: break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest
def build_heap(arr):
    for i in range(len(arr)//2 - 1, -1, -1):
        heapify_down(arr, i)

Speed No steps

Value:

Code Implementation

Below are implementations of a max-heap with insert and extract_max operations. The array-based approach makes the code straightforward — parent and child indices are computed with simple arithmetic.

class MaxHeap:
    def __init__(self):
        self.heap = []

    def _parent(self, i):
        return (i - 1) // 2

    def _left(self, i):
        return 2 * i + 1

    def _right(self, i):
        return 2 * i + 2

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def insert(self, value):
        """Insert a value and bubble up to restore heap property."""
        self.heap.append(value)
        idx = len(self.heap) - 1
        # Bubble up
        while idx > 0 and self.heap[idx] > self.heap[self._parent(idx)]:
            self._swap(idx, self._parent(idx))
            idx = self._parent(idx)

    def extract_max(self):
        """Remove and return the maximum element (root)."""
        if not self.heap:
            raise IndexError("extract_max from empty heap")
        max_val = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._sink_down(0)
        return max_val

    def _sink_down(self, idx):
        """Sink a node down to its correct position."""
        n = len(self.heap)
        while True:
            largest = idx
            left = self._left(idx)
            right = self._right(idx)
            if left < n and self.heap[left] > self.heap[largest]:
                largest = left
            if right < n and self.heap[right] > self.heap[largest]:
                largest = right
            if largest == idx:
                break
            self._swap(idx, largest)
            idx = largest

    def peek(self):
        """Return the maximum element without removing it."""
        if not self.heap:
            raise IndexError("peek from empty heap")
        return self.heap[0]


# Example usage
h = MaxHeap()
for val in [40, 70, 30, 90, 50, 80, 60]:
    h.insert(val)

print("Max:", h.peek())            # Output: Max: 90
print("Extracted:", h.extract_max()) # Output: Extracted: 90
print("New max:", h.peek())         # Output: New max: 80

Complexity Analysis

Since a heap is a complete binary tree, its height is always O(log n). Both insert and extract operations traverse at most one root-to-leaf path, bounding their cost. The build-heap operation achieves O(n) through a clever bottom-up approach where most nodes are near the leaves and require very few swaps.

Operation	Time Complexity	Space Complexity	Description
Insert	O(log n)	O(n)	Add element at the end, bubble up at most log n levels
Extract-Max	O(log n)	O(n)	Swap root with last, sink down at most log n levels
Peek	O(1)	O(n)	Maximum is always at index 0 (the root)
Build Heap	O(n)	O(n)	Bottom-up heapify; sum of sift-down costs converges to O(n)
Space	—	O(n)	Array of n elements; no additional pointer overhead

Heaps are especially efficient as priority queues: they support insert and delete-max (or delete-min) in O(log n) time, with O(1) access to the extremal element. This makes them ideal for task schedulers, event-driven simulations, and graph algorithms like Dijkstra and Prim.

Real-World Applications

🏥

Task Scheduling OS schedulers use a min-heap to pick the highest-priority process

🗺️

Dijkstra's Algorithm Shortest-path finds the minimum-weight edge using a min-heap

📈

Top-K Elements "Find top 10 most-visited pages" solved with a size-10 min-heap

🔄

Heap Sort Sorting algorithm built directly on the heap data structure

Practice

Find the kth largest element in an unsorted array (1-indexed, so k=1 means the largest).

Given a list of sorted lists, merge them all into a single sorted list and return it.

Quiz

Test your understanding of heaps with these questions.

Q1. In a max-heap stored as an array, which element is guaranteed to be the largest?

The last element in the array

The middle element of the array

The first element (index 0)

It could be anywhere in the array

In a max-heap, the heap property guarantees that every parent is greater than or equal to its children. Since the root (index 0) is the ancestor of all other nodes, it must hold the largest value in the entire heap.

Q2. For a node at index i in a zero-indexed heap array, where is its left child?

2i

2i + 1

2i + 2

i / 2

In a zero-indexed array representation of a complete binary tree, the left child of node at index i is at 2i + 1, and the right child is at 2i + 2. The formula 2i is used when the array is 1-indexed (starting from index 1).

Q3. What is the time complexity of building a max-heap from an unsorted array of n elements?

O(n)

O(n log n)

O(n²)

O(log n)

Although building a heap involves calling sift-down for each non-leaf node, the total work is O(n). This is because most nodes are near the bottom of the tree and require very few swaps. A mathematical analysis shows the sum of sift-down costs across all levels converges to O(n), not the naive O(n log n) estimate.

Q4. After inserting a new element into a max-heap, which operation restores the heap property?

Sink down from the root

Rotate the tree

Re-sort the entire array

Bubble up from the inserted position

When a new element is added at the end of the heap array, it might be larger than its parent, violating the max-heap property. The bubble-up operation repeatedly swaps the element with its parent until the property is restored or the element reaches the root. Sink-down is used during extract-max, not insert.

Q5. A max-heap has the array representation [100, 80, 90, 40, 50, 60, 30]. After extracting the maximum, what will the root be?

80

30

90

60

Extract-max removes 100 (the root), swaps 30 (last element) into the root position, giving [30, 80, 90, 40, 50, 60]. Then sink-down: 30 is compared with children 80 and 90. Since 90 is the largest child, swap 30 and 90 → [90, 80, 30, 40, 50, 60]. Then 30 is compared with child 60, swap again → [90, 80, 60, 40, 50, 30]. The new root is 90.