Binary Heap

A Binary Heap is a complete binary tree that satisfies the heap property. It is a data structure commonly used to implement priority queues. There are two main types of binary heaps: the min-heap and the max-heap.

Properties

• Complete Binary Tree: A binary heap is a complete binary tree, meaning all levels of the tree are fully filled except possibly for the last level, which is filled from left to right.
• Heap Property:
  • Min-Heap: In a min-heap, the value of each node is greater than or equal to the value of its parent. The minimum element is at the root.
  • Max-Heap: In a max-heap, the value of each node is less than or equal to the value of its parent. The maximum element is at the root.

Operations

1. Insertion: Add a new element to the heap while maintaining the heap property.
2. Extraction: Remove the root element (minimum or maximum) and reorganize the heap.
3. Heapify: Maintain the heap property after an operation.

Min-Heap Example

     1
   /   \
  3     5
 / \   / \
7   9 8  10

Max-Heap Example

     10
   /    \
  9      8
 / \    / \
7   6  5   4

Below class handles MinHeap, MaxHeap, MinHeapPriorityQueue and MaxHeapPriorityQueue

class MinMaxPriorityQueue {

  #heap = []
  #compare;

  constructor(compare = (a, b) => a - b) {
    this.#compare = compare; // Default to Min-Heap if no compare function is provided
  }

  // Add a new element to the priority queue
  enqueue = (value) => {
    this.#heap.push(value);
    this.#heapifyUp(this.#heap.length - 1);
  }

  // Remove and return the element with the highest priority (smallest for min-heap, largest for max-heap)
  dequeue = () => {
    if (this.#heap.length === 0) return null;
    const root = this.#heap[0];
    const end = this.#heap.pop();
    if (this.#heap.length > 0) {
      this.#heap[0] = end;
      this.#heapifyDown(0);
    }
    return root;
  }

  // Peek at the element with the highest priority without removing it
  peek = () => {
    return this.#heap.length > 0 ? this.#heap[0] : null;
  }

  // Check if the priority queue is empty
  isEmpty = () => {
    return this.#heap.length === 0;
  }

  // Get the size of the priority queue
  size = () => {
    return this.#heap.length;
  }

  // Get the heap
  get heap() {
    return this.#heap;
  }
  
  // Maintain heap property by moving element up
  #heapifyUp = (index) => {
    let parent = Math.floor((index - 1) / 2);
    while (index > 0 && this.#compare(this.#heap[index], this.#heap[parent]) < 0) {
      this.#swap(index, parent)
      index = parent;
      parent = Math.floor((index - 1) / 2);
    }
  }

  // Maintain heap property by moving element down
  #heapifyDown = (index) => {
    const length = this.#heap.length;
    let left = 2 * index + 1;
    let right = 2 * index + 2;
    let extreme = index;

    if (left < length && this.#compare(this.#heap[left], this.#heap[extreme]) < 0) {
      extreme = left;
    }

    if (right < length && this.#compare(this.#heap[right], this.#heap[extreme]) < 0) {
      extreme = right;
    }

    if (extreme !== index) {
      this.#swap(index, extreme)
      this.#heapifyDown(extreme);
    }
  }

  #swap = (i, j) => {
    [this.#heap[i], this.#heap[j]] = [this.#heap[j], this.#heap[i]]
  }
}

List to practice Heap

• https://leetcode.com/problem-list/ah220lmv/