Heap (Priority Queue) — Data Structures

About A heap is a complete binary tree that satisfies the heap property: in a max-heap, every parent node is greater than or equal to its children (root is maximum)

A heap is a complete binary tree that satisfies the heap property: in a max-heap, every parent node is greater than or equal to its children (root is maximum).

In a min-heap, every parent is smaller than its children (root is minimum).

Heaps are the classic implementation of priority queues.

How It Works

Heaps are typically stored in an array where index `i`'s children are at `2i+1` (left) and `2i+2` (right), and its parent is at `floor((i-1)/2)`.

Insertion adds at the end and "bubbles up" (swaps with parent) until the heap property is restored.

Extraction removes the root, moves the last element to the root, and "bubbles down" (swaps with the larger/smaller child) to restore order.

Building a heap from an unsorted array runs in O(n) using Floyd's algorithm.

Time & Space Complexities

Operation	Time	Space
Insert	O(log n)	O(1)
Extract Max/Min	O(log n)	O(1)
Peek (root)	O(1)	O(1)
Build Heap (Floyd)	O(n)	O(1)

Best Use Cases

Priority queues (scheduling, Dijkstra, A*)
HeapSort algorithm (O(n log n) sort)
K-th largest/smallest element in stream
Median maintenance (two heaps pattern)
Task scheduling with priorities (OS kernel)

Worked Example

Insert 85 and extract max from max-heap [95, 62, 48, 45, 31, 27, 18]

Input: array heap (max-heap); root 95 at index 0

1 Insert 85: append it at the end, then bubble up — 85 > its parent 48, so swap; now 85 > parent 95? No, stop.
2 The heap becomes [95, 85, 48, 62, 31, 27, 18, 45].
3 Extract max: take the root 95, move the last element (45) to the root, and bubble it down.
4 45 compares with children 85 and 48; swap with 85, then with 62, then with 31 — stopping when both children are smaller.
5 The heap property is restored after each operation.

Result: After insert + extract, the root is 85; both operations run in O(log n).

Pseudocode

Insert (Max-Heap)

function insert(heap, value):
    heap.append(value)
    idx = heap.length - 1
    while idx > 0 and heap[parent(idx)] < heap[idx]:
        swap heap[parent(idx)], heap[idx]
        idx = parent(idx)

function parent(i): return floor((i - 1) / 2)

Extract Max

function extractMax(heap):
    if heap is empty: error "Empty heap"
    max = heap[0]
    heap[0] = heap[heap.length - 1]
    heap.pop()
    bubbleDown(heap, 0)
    return max

function bubbleDown(heap, idx):
    while true:
        largest = idx
        left = 2*idx + 1
        right = 2*idx + 2
        if left < heap.length and heap[left] > heap[largest]:
            largest = left
        if right < heap.length and heap[right] > heap[largest]:
            largest = right
        if largest == idx: break
        swap heap[idx], heap[largest]
        idx = largest

Build Heap (Floyd)

function buildHeap(array):
    n = array.length
    for i = floor(n/2) - 1 down to 0:
        bubbleDown(array, i)
    return array

Heap Visualizer

Insert

Value:

Speed 100ms

Step Progress 0 / 0

Heap Size 0

Swaps 0

Status Ready

Element

Comparing

Swapping

Active

Step Explanation

Select an operation to begin.

Pseudocode