**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 : (https://www.youtube.com/@code-with-Bharadwaj)↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
#### 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
**Find k-th smallest/largest element
**Priority-based tasks (Dijkstra’s Algorithm, Huffman Coding) === Min Heap
**Merge k Sorted Lists
**Sliding Window Maximum
**Job Scheduling Problems
↵
↵
↵
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 :
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
