๐๏ธ Heap (Priority Queue)
One-line summary: A complete binary tree satisfying the heap property โ O(log n) insert and extract-min/max, the engine behind Top-K, median, K-way merge, and scheduling algorithms.
Diagramโ
Conceptโ
- Min-heap: parent โค children โ
peek()is minimum. - Max-heap: parent โฅ children โ
peek()is maximum. - JavaScript has no native heap โ simulate with sorted array or use
@datastructures-js/priority-queue.
Key operations: insert O(log n), extractMin/Max O(log n), peek O(1), heapify O(n).
Time & Space Complexityโ
| Operation | Time | Space |
|---|---|---|
| Insert | O(log n) | O(1) |
| Extract min/max | O(log n) | O(1) |
| Peek | O(1) | O(1) |
| Heapify | O(n) | O(1) |
| Top-K elements | O(n log k) | O(k) |
| K-way merge (n total, k lists) | O(n log k) | O(k) |
Common Patternsโ
Pattern 1 โ Top-K Frequent (Min-Heap of size K)โ
function topKFrequent(nums, k) {
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
return [...freq.entries()]
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map(([num]) => num);
}
Pattern 2 โ Two Heaps (Median from Stream)โ
// maxHeap = lower half, minHeap = upper half
// Invariant: |maxHeap.size - minHeap.size| <= 1
// Median = maxHeap.top() or avg of both tops
Pattern 3 โ K-way Mergeโ
// 1. Add first element from each list to min-heap with [value, listIdx, elemIdx]
// 2. Extract min โ push to result โ add next element from same list
// 3. Repeat until heap empty
Pitfallsโ
- JS has no native heap โ off-the-shelf sort trick is O(n log n), not O(n log k)
- Rebalancing Two Heaps: ensure size diff โค 1 after every insert
- K-way merge: track which list each heap element came from
Practice Problemsโ
Related Topicsโ
- Trees โ heap is a complete binary tree
- Sorting โ heapsort uses heap operations
- Graphs โ Dijkstra uses min-heap
Heap Data Structure Referenceโ
The following notes and runnable implementations (with tests) live alongside this guide in this folder.
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property described below.
In a min heap, if P is a parent node of C, then the key (the value) of P is less than or equal to the key of C.
In a max heap, the key of P is greater than or equal to the key of C.
The node at the "top" of the heap with no parents is called the root node.
Time Complexitiesโ
Here are time complexities of various heap data structures. Function names assume a max-heap.
| Operation | find-max | delete-max | insert | increase-key | meld |
|---|---|---|---|---|---|
| Binary | ฮ(1) | ฮ(log n) | O(log n) | O(log n) | ฮ(n) |
| Leftist | ฮ(1) | ฮ(log n) | ฮ(log n) | O(log n) | ฮ(log n) |
| Binomial | ฮ(1) | ฮ(log n) | ฮ(1) | O(log n) | O(log n) |
| Fibonacci | ฮ(1) | ฮ(log n) | ฮ(1) | ฮ(1) | ฮ(1) |
| Pairing | ฮ(1) | ฮ(log n) | ฮ(1) | o(log n) | ฮ(1) |
| Brodal | ฮ(1) | ฮ(log n) | ฮ(1) | ฮ(1) | ฮ(1) |
Where:
- find-max (or find-min): find a maximum item of a max-heap, or a minimum item of a min-heap, respectively (a.k.a. peek)
- delete-max (or delete-min): removing the root node of a max heap (or min heap), respectively
- insert: adding a new key to the heap (a.k.a., push)
- increase-key or decrease-key: updating a key within a max- or min-heap, respectively
- meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.
In this repository, the MaxHeap.js and MinHeap.js are examples of the Binary heap.
Implementationโ
- MaxHeap.js and MinHeap.js
- MaxHeapAdhoc.js and MinHeapAdhoc.js โ the minimalistic (ad hoc) version of a MinHeap/MaxHeap data structure that doesn't have external dependencies and is easy to copy-paste and use during a coding interview.
Referencesโ
โ Back to Home ยท ยฉ sparshjaswal