• -------------------------------------------------------- / / ( The Authentic JS CodeBuff ) ___ _ _ _ | _ ) |_ __ _ _ _ __ _ | |_ __ ____ _ (_) | _ \ ' \/ _| '_/ _ / \ V V / _ || | |/_||___,_|_| __,___,_|_/_/__,_|/ | |__/ / / --------------------------------------------------------- / / Youtube: https://youtube.com/@code-with-Bharadwaj / / Github : https://github.com/Manu577228 / / ----------------------------------------------------------- */

Heaps are essential data structures for efficient problem-solving in competitive programming.

They shine when you need to repeatedly access the smallest or largest element in a collection.

This blog post will explore max heaps and min heaps, their implementation in Node.js, and how they can give you an edge in coding contests.

What are Heaps? A heap is a specialized tree-based data structure that satisfies the heap property:

• Min Heap: The value of each node is less than or equal to the value of its children. The smallest element is always at the root.

• Max Heap: The value of each node is greater than or equal to the value of its children. The largest element is always at the root.

Heaps are typically implemented using arrays, which allows for efficient access to elements and simplifies parent-child relationships.

Node.js and Heaps

While Node.js doesn't have a built-in heap implementation in its standard library, we can easily create one.

Since performance is crucial in competitive programming, we'll focus on a reasonably optimized approach.

class MinHeap { constructor() { this.heap = []; }

size() { return this.heap.length; }

peek() { return this.heap[0]; }

push(value) { this.heap.push(value); this.bubbleUp(this.heap.length — 1); }

pop() { const top = this.heap[0]; const last = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = last; this.bubbleDown(0); } return top; }

bubbleUp(index) { const parent = Math.floor((index — 1) / 2); if (parent >= 0 && this.heap[index] < this.heap[parent]) { [this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]]; this.bubbleUp(parent); } }

bubbleDown(index) { const left = 2 * index + 1; const right = 2 * index + 2; let smallest = index;

if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
  smallest = left;
}
if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
  smallest = right;
}

if (smallest !== index) {
  [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
  this.bubbleDown(smallest);
}

} }

// MaxHeap implementation (similar structure, just change the comparisons)

class MaxHeap extends MinHeap { bubbleUp(index) { const parent = Math.floor((index — 1) / 2); if (parent >= 0 && this.heap[index] > this.heap[parent]) { // Note the > here [this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]]; this.bubbleUp(parent); } }

bubbleDown(index) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let largest = index; // Changed to largest

    if (left < this.heap.length && this.heap[left] > this.heap[largest]) { // Note the > here
      largest = left;
    }
    if (right < this.heap.length && this.heap[right] > this.heap[largest]) { // Note the > here
      largest = right;
    }

    if (largest !== index) {
      [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
      this.bubbleDown(largest);
    }
  }

}

Competitive Programming Applications

• Finding the Kth Largest/Smallest Element:

Heaps excel at this. Use a min-heap for the Kth largest and a max-heap for the Kth smallest.

• Median Maintenance:

Maintain a min-heap for the larger half of the elements and a max-heap for the smaller half. The medians are at the roots.

• Dijkstra's Algorithm:

Heaps are crucial for efficient implementation of Dijkstra's shortest path algorithm.

• Priority Queues:

Heaps are the perfect underlying structure for priority queues.

Example: Kth Largest Element

function kthLargest(nums, k) { const minHeap = new MinHeap(); for (const num of nums) { minHeap.push(num); if (minHeap.size() > k) { minHeap.pop(); } } return minHeap.peek(); }

const nums = [3, 2, 1, 5, 6, 4]; const k = 2; console.log(kthLargest(nums, k)); // Output: 5

Conclusion :

Understanding and implementing heaps is a valuable skill for any competitive programmer.

This blog post provided a clear implementation of min and max heaps in Node.js, ready to be used in your next coding contest.

Practice using them in different problems to solidify your understanding and unlock their full potential!

Happy Coding ( By Bharadwaj )
            YOUTUBE : https://youtube.com/@code-with-Bharadwaj