Binary Heap

What is Binary Heap

Binary Heap is a complete binary tree that satisfies the heap property: every node is greater than (or less than) its children. This makes the heap an ideal structure for implementing priority queues.

It was proposed by J.W.J. Williams in 1964 as the basis for the HeapSort algorithm.

Two Types of Heap

Key Properties

Array Storage

Main feature: the tree is stored in a regular array, without pointers:

        1
       / \
      3   2
     / \ / \
    7  4 5  6

Array: [ _, 1, 3, 2, 7, 4, 5, 6 ]  (1-based indexing)
        0  1  2  3  4  5  6  7

Index Navigation:

For a node at index i:
┌─────────────────────────────────┐
│  Parent      →  i / 2           │
│  Left child  →  2 * i           │
│  Right child →  2 * i + 1       │
└─────────────────────────────────┘

(for 0-based indexing: parent = (i-1)/2, left = 2i+1, right = 2i+2)

Max-Heap Visualization

Array: [100, 85, 90, 70, 60, 75, 80, 40, 50, 55]
Index:   0    1   2   3   4   5   6   7   8   9

Basic Operations

🔼 Sift Up (bubble up) — auxiliary

Used after insertion: a new element is added to the end and "bubbles up" to its correct position.

Inserting 95 into Max-Heap:

[100, 85, 90, 70, 60, 75, 80, 40, 50, 55, 95]
                                           ↑ added to the end

95 > 60 (parent) → swap
95 > 85 (parent) → swap
95 < 100 (parent) → stop

Result: [100, 95, 90, 70, 85, 75, 80, 40, 50, 55, 60]

def sift_up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:      # for Max-Heap
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

🔽 Sift Down (percolate down) — auxiliary

Used after root removal: the last element is placed at the root and "sinks down" to its correct position.

Removing root 100:
  Place last element (60) at the root
  [60, 95, 90, 70, 85, 75, 80, 40, 50, 55]

  60 < max(95, 90) = 95 → swap with left child
  [95, 60, 90, 70, 85, 75, 80, 40, 50, 55]

  60 < max(70, 85) = 85 → swap with right child
  [95, 85, 90, 70, 60, 75, 80, 40, 50, 55]

  60 > no children → stop  ✓

def sift_down(heap, i, n):
    while True:
        largest = i
        left, right = 2*i + 1, 2*i + 2
        if left < n and heap[left] > heap[largest]:
            largest = left
        if right < n and heap[right] > heap[largest]:
            largest = right
        if largest == i:
            break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest

➕ Insertion — O(log n)

1. Add element to the end of the array
2. Sift Up from the added element

def push(heap, val):
    heap.append(val)
    sift_up(heap, len(heap) - 1)

🏆 Get Max/Min — O(1)

def peek(heap):
    return heap[0]    # just check the root

🗑️ Root Removal (Extract Max/Min) — O(log n)

1. Remember the root (result)
2. Put the last element in the root position
3. Decrease heap size by 1
4. Sift Down from the root

def pop(heap):
    heap[0], heap[-1] = heap[-1], heap[0]
    val = heap.pop()
    sift_down(heap, 0, len(heap))
    return val

🏗️ Heapify (Build Heap) — O(n)

Naive way (n insertions) = O(n log n)
Optimal way (Floyd, 1964) = O(n) — sift_down from middle to root:

def heapify(arr):
    n = len(arr)
    # Start from the last internal node
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

Why O(n)? Most nodes are leaves (n/2 nodes), 
which perform 0 operations. Nodes above perform O(1), O(2)...
Total: O(n) based on geometric progression formula.

HeapSort — O(n log n)

The heap is the basis of a classic sorting algorithm:

1. Build Max-Heap from array     → O(n)
2. n times: extract maximum      → O(n log n)
   - swap root with last element
   - decrease heap size
   - sift_down

In-place sorting, no additional memory!

def heap_sort(arr):
    n = len(arr)
    heapify(arr)                           # O(n)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]   # root to the end
        sift_down(arr, 0, i)              # O(log n)

Operation Complexity

{
  "title": { "text": "Binary Heap Operation Complexity", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["O(1)", "O(log n)", "O(n)"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "data": ["1K", "10K", "100K", "1M", "10M"]
  },
  "yAxis": {
    "type": "value",
    "name": "Operations"
  },
  "series": [
    {
      "name": "O(1)",
      "type": "line",
      "data": [1, 1, 1, 1, 1],
      "smooth": true,
      "lineStyle": { "color": "#5cb85c", "width": 3 }
    },
    {
      "name": "O(log n)",
      "type": "line",
      "data": [10, 13, 17, 20, 23],
      "smooth": true,
      "lineStyle": { "color": "#f0ad4e", "width": 3 }
    },
    {
      "name": "O(n)",
      "type": "line",
      "data": [1000, 10000, 100000, 1000000, 10000000],
      "smooth": true,
      "lineStyle": { "color": "#d9534f", "width": 2, "type": "dashed" }
    }
  ]
}

Pros and Cons

Where It is Used

Final Comparison of All Four Structures