logo
SEE ALGORITHMS

Binary Heap Visualization

A Binary Heap is a complete binary tree (typically stored in an array), where each node satisfies the heap property: in a Max-Heap, parents are greater than or equal to their children, while in a Min-Heap, parents are less than or equal to their children. Heap Sort utilizes this structure by building a Max-Heap and repeatedly extracting the root element to the end of the array, resulting in an efficient O(n log n) in-place sorting algorithm.

Because a binary heap is a complete binary tree (all levels are completely filled except possibly the lowest, which is filled from left to right), it requires no pointers and is compactly packed in an array. Beyond sorting, binary heaps are the canonical data structure for implementing high-performance priority queues.


Pseudocode

function insert(value):
    arr[n] = value
    i = n, n = n + 1
    while i > 0:
        parent = (i - 1) / 2
        if arr[parent] >= arr[i]:
            break
        swap(parent, i)
        i = parent
function extract():
    if n == 0: return null
    max = arr[0]
    arr[0] = arr[n - 1]
    n = n - 1
    heapifyDown(0)
    return max

Visualizer


AI Summary

(3 credits)

See what happens with your input

Get a short, step-by-step explanation of this visualization. Turn on AI Summary, then start a fresh run with your input.


How It Works

During insertion, the new value is appended to the end of the array (the next open leaf). It is then repeatedly swapped with its parent (heapify-up) as long as it is strictly greater than the parent (in a Max-Heap). This bubbling-up takes at most O(log n) steps, bounded by tree height.

During extraction, the root element (the maximum) is removed. The last element in the array is moved to the root to preserve the complete tree shape, and is then sifted down (heapify-down) by swapping with its largest child until the heap invariant is restored.

When to Use

Binary Heaps are the industry standard for implementing Priority Queues, where rapid retrieval of the highest (or lowest) priority item is essential. They power greedy graph algorithms like Dijkstra's shortest path and Prim's minimum spanning tree. Operating system kernels rely on heaps for timer wheels and process scheduling, and stream-processing engines use paired min/max heaps to track running medians in real time.

Time & Space Complexity

Metric / Operation
Complexity
Description
InsertionO(log n)Appends to the array end and bubbles upward (heapify-up) across at most log₂ n levels.
Extract Max/MinO(log n)Replaces the root with the last element and sifts downward (heapify-down) across at most log₂ n levels.
Build HeapO(n)Floyd’s bottom-up construction builds a heap in linear time by sifting down non-leaf nodes.
Space ComplexityO(n)Stored in a contiguous array without pointer overhead, requiring O(1) auxiliary space.

Common Interview Questions

How is a complete Binary Heap represented efficiently using an array without explicit child pointers?

For a parent at index i in a 0-indexed array, left child is at 2i + 1, right child is at 2i + 2, and parent is at (i - 1) / 2. This eliminates the need for explicit child pointers, reducing memory usage.

What is the time complexity of insert, extract, and peek operations in a Binary Heap?

peek(): O(1) (root element). insert(): O(log n) (heapify-up). extract(): O(log n) (replace root with last element and heapify-down).

How do you find the K largest elements in an unsorted stream of N elements efficiently?

Maintain a Min-Heap of size K. Iterate through the stream: if an element is larger than the root of the Min-Heap, replace the root and heapify. Final Min-Heap contains the K largest elements in O(N log K) time and O(K) space.


💬  Discussion

to join the discussion


Curious to Learn More?

Hand-picked resources to deepen your understanding


Learn DSA on Udemy
Learn DSA on Udemy
As an Udemy Associate, I earn from qualifying purchases.

© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0