Introduction to Heaps

[!NOTE] This module explores the core principles of Introduction to Heaps, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Hook: The Sorted Hierarchy

We’ve learned Binary Search Trees (O(log N) search). But what if you only ever care about the best item?

  • The highest priority task in a CPU.
  • The shortest path in a navigation app.
  • The next customer in a service line.

A Binary Heap is a specialized tree that gives you instant O(1) access to the extremum (Min or Max) while maintaining a partial order in O(log N). It is the backbone of the Priority Queue.

2. The 4 Pillars of Heap Mastery

Pillar Focus Why it matters
1. Intuition Shape vs. Order Balancing the “Complete Tree” and “Heap Property.”
2. Rigor Heapify Complexity Proving why building a heap is O(N), not O(N log N).
3. Hardware Array Mapping Eliminating pointer overhead for 100% cache locality.
4. Patterns Top K & Medians Using heaps to process massive streams efficiently.

3. The Magic: Array Representation

Unlike generic trees (nodes + pointers), Heaps are usually stored as Arrays.

  • Root: Index 0
  • Left Child: 2*i + 1
  • Right Child: 2*i + 2
  • Parent: (i-1) / 2

4. The Mathematical Anchor: Index Arithmetic

Why do we use 2i + 1? And what happened to the famous 2i formula?

1-Based Indexing (The Classic)

In many academic texts, heaps start at index 1.

  • Left: 2i
  • Right: 2i + 1
  • Parent: ⌊ i/2 ⌋

0-Based Indexing (Modern/Code)

Since arrays in almost all languages (Java, Go, Python, C++) start at 0, the formula shifts:

  • Left: 2i + 1
  • Right: 2i + 2
  • Parent: ⌊ (i-1)/2 ⌋

[!TIP] Complete Tree Property: Because heaps fill every level before moving to the next, we never have “gaps” in the array. This makes the math exact and the storage 100% efficient.

5. Interactive: Heap Array Visualizer

See how the Tree maps to the Array. Hover over a node to highlight its parent and children in the array.

Logical View (Tree)

Physical View (Array)

Hover over nodes.

6. Implementation (Go)

Java has PriorityQueue. Go has container/heap.

Java

// Java uses a Min Heap by default
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

minHeap.offer(10); // Insert
minHeap.offer(5);

int min = minHeap.peek(); // 5
int removed = minHeap.poll(); // 5

Go

import "container/heap"

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // Min Heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
  *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

// Usage
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
min := heap.Pop(h).(int) // 1