Min Heap & Max Heap...
Heap is a fundamental data structure that is widely used in competitive programming, especially in problems that require efficient retrieval of the smallest or largest elements in a dataset.
####
JavaScript does not have a built-in heap implementation, but we can efficiently implement Min Heap and Max Heap using an array and a comparator function.
In this blog, we will cover:
What is a Heap?
Min Heap & Max Heap with Implementation in JavaScript (Node.js).
Advantages & Disadvantages of Heaps.
When to Use Heaps in Codeforces Problems.
Why & When NOT to Use Heaps.
1. What is a Heap?
A Heap is a special type of binary tree-based data structure that satisfies the heap property:
- Min Heap: The parent node is always smaller than or equal to its child nodes.
- Max Heap: The parent node is always larger than or equal to its child nodes.
This property ensures that the smallest (Min Heap) or largest (Max Heap) element is always at the root, making heaps extremely useful for priority-based tasks.
2. Min Heap & Max Heap Implementation in JavaScript (Node.js)
Since JavaScript does not provide a built-in heap, we implement it using an array-based binary heap with the following operations:
- Insert (push)
- Extract Min/Max (pop)
- Heapify (maintain heap property)
Min Heap Implementation
class MinHeap { constructor() { this.h = []; }
push(v) {
this.h.push(v);
this.#heapifyUp();
}
pop() {
if (this.h.length === 0) return null;
if (this.h.length === 1) return this.h.pop();
const min = this.h[0];
this.h[0] = this.h.pop();
this.#heapifyDown();
return min;
}
top() {
return this.h.length ? this.h[0] : null;
}
size() {
return this.h.length;
}
#heapifyUp() {
let i = this.h.length - 1;
while (i > 0) {
let p = Math.floor((i - 1) / 2);
if (this.h[p] <= this.h[i]) break;
[this.h[p], this.h[i]] = [this.h[i], this.h[p]];
i = p;
}
}
#heapifyDown() {
let i = 0;
while (2 * i + 1 < this.h.length) {
let j = 2 * i + 1;
if (j + 1 < this.h.length && this.h[j + 1] < this.h[j]) j++;
if (this.h[i] <= this.h[j]) break;
[this.h[i], this.h[j]] = [this.h[j], this.h[i]];
i = j;
}
}}
// Usage:
let heap = new MinHeap(); heap.push(5); heap.push(3); heap.push(8); heap.push(1); console.log(heap.pop()); // 1 console.log(heap.pop()); // 3
Max Heap Implementation
A Max Heap follows the same structure as a Min Heap, but the parent nodes must always be greater than the child nodes.
class MaxHeap { constructor() { this.h = []; }
push(v) {
this.h.push(v);
this.#heapifyUp();
}
pop() {
if (this.h.length === 0) return null;
if (this.h.length === 1) return this.h.pop();
const max = this.h[0];
this.h[0] = this.h.pop();
this.#heapifyDown();
return max;
}
top() {
return this.h.length ? this.h[0] : null;
}
size() {
return this.h.length;
}
#heapifyUp() {
let i = this.h.length - 1;
while (i > 0) {
let p = Math.floor((i - 1) / 2);
if (this.h[p] >= this.h[i]) break;
[this.h[p], this.h[i]] = [this.h[i], this.h[p]];
i = p;
}
}
#heapifyDown() {
let i = 0;
while (2 * i + 1 < this.h.length) {
let j = 2 * i + 1;
if (j + 1 < this.h.length && this.h[j + 1] > this.h[j]) j++;
if (this.h[i] >= this.h[j]) break;
[this.h[i], this.h[j]] = [this.h[j], this.h[i]];
i = j;
}
}}
// Usage:
let heap = new MaxHeap(); heap.push(5); heap.push(3); heap.push(8); heap.push(1); console.log(heap.pop()); // 8 console.log(heap.pop()); // 5
3. Advantages & Disadvantages of Heaps
Pros (Why Use a Heap?)
- Efficient Priority Queue: Inserting and extracting the smallest/largest element is O(log N).
- Useful for Shortest Path & Scheduling: Heaps are widely used in Dijkstra’s Algorithm and task scheduling problems.
- Memory Efficient: Unlike balanced BSTs, heaps require less memory overhead due to the array-based structure.
Cons (When NOT to Use a Heap?)
- Not Ideal for Searching: Finding an arbitrary element is O(N), unlike BSTs where searching is O(log N).
- Limited Sorting Use: Although Heap Sort exists, it’s generally outperformed by Merge Sort & Quick Sort in practice.
- No Ordered Traversal: Unlike BSTs, you cannot traverse elements in sorted order efficiently.
4. When to Use Heaps in Codeforces?
Common Problem Scenarios
Problem Type ================================================== Use Case Find k-th smallest/largest element ============================ Min Heap / Max Heap Priority-based tasks (Dijkstra’s Algorithm, Huffman Coding) === Min Heap Merge k Sorted Lists ========================================== Min Heap Sliding Window Maximum ======================================== Max Heap Job Scheduling Problems ======================================= Min Heap
Example: Finding k-th Smallest Element
let heap = new MinHeap(); for (let x of [7, 10, 4, 3, 20, 15]) heap.push(x); let k = 3; while (--k) heap.pop(); console.log(heap.pop()); // 7
5. Why & When NOT to Use Heaps?
- If You Need Fast Searching: Use BSTs or Hash Maps for O(1) / O(log N) searches.
- If You Need Ordered Data: Use a Balanced BST (e.g., AVL, Red-Black Tree) instead.
- For Sorting Large Arrays: Use Quick Sort or Merge Sort instead of Heap Sort.
10 Scenarios Where Heaps Are Used in Competitive Programming
- Finding the k-th Smallest or k-th Largest Element
- Merging k Sorted Arrays
- Implementing a Priority Queue
- Dijkstra’s Algorithm (Shortest Path in a Graph)
- Prim’s Algorithm (Minimum Spanning Tree — MST)
- Top k Frequent Elements (Frequency Counting)
- Median of a Stream (Dynamic Median Calculation)
- Job Scheduling with Deadlines (Greedy Scheduling)
- Sliding Window Maximum (Finding Max in Every Window of Size k)
- Huffman Encoding (Data Compression — Huffman Coding Tree)
Conclusion
Min Heap and Max Heap are powerful tools in competitive programming, particularly for priority-based tasks, shortest path algorithms, and scheduling problems. However, they should not be used for searching or problems requiring sorted order access. By implementing a heap efficiently in JavaScript, you can significantly improve your performance on Codeforces.
Happy Coding !
Youtube : (http://www.youtube.com/@code-with-Bharadwaj)
