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
Go
```java // Java uses a Min Heap by default PriorityQueue minHeap = new PriorityQueue<>(); minHeap.offer(10); // Insert minHeap.offer(5); int min = minHeap.peek(); // 5 int removed = minHeap.poll(); // 5 ``` </div>
```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 ```
</div>