Data Structures #4 — Binary Heap & Priority Queue

A binary heap is a complete binary tree stored in an array where every parent is smaller (min-heap) or larger (max-heap) than its children. It's the data structure behind priority queues, used in Dijkstra's algorithm, task schedulers, and event loops.

1. The Array Layout — Parent/Child Index Math

The heap is stored as an array where for any node at index i:

• Parent: Math.floor((i - 1) / 2)
• Left child: 2 * i + 1
• Right child: 2 * i + 2

2. Min-Heap Implementation

3. Priority Queue Built on Min-Heap

4. Heapify — Build a Heap from an Array in O(n)

Key Takeaways

• Heap is stored as an array — no pointers needed. Parent at (i-1)/2, children at 2i+1 and 2i+2.
• Insert: push to end, bubble up — O(log n).
• Extract min: swap root with last, pop, sink down — O(log n).
• Heapify: build heap from unsorted array in O(n) — start from last non-leaf and sink down.
• Priority queue = min-heap where each element has a priority value.
• JavaScript has no built-in heap/priority queue — this implementation is commonly needed for LeetCode problems.

Next: Data Structures #5 — Trie (Prefix Tree) — insert, search, startsWith, and autocomplete.