Heap

A Heap is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is less than or equal to its own value.

Heaps are often used to implement priority queues, where the smallest (or largest) element is always at the root of the tree.

Types of heaps:

Generally, heaps are of two types.

Max-Heap:

In this heap, the value of the root node must be the greatest among all its child nodes and the same thing must be done for its left and right sub-tree also.

The total number of comparisons required in the max heap is according to the height of the tree.

The height of the complete binary tree is always logn; therefore, the time complexity would also be O(logn).

Min-Heap:

In this heap, the value of the root node must be the smallest among all its child nodes and the same thing must be done for its left and right sub-tree also.

The total number of comparisons required in the min heap is according to the height of the tree.

The height of the complete binary tree is always logn; therefore, the time complexity would also be O(logn).

Properties of Heap:

Heap has the following Properties:

• Complete Binary Tree: A heap tree is a complete binary tree, meaning all levels of the tree are fully filled except possibly the last level, which is filled from left to right. This property ensures that the tree is efficiently represented using an array.

• Heap Property: This property ensures that the minimum (or maximum) element is always at the root of the tree according to the heap type.

• Parent-Child Relationship: The relationship between a parent node at index ‘i’ and its children is given by the formulas: left child at index 2i+1 and right child at index 2i+2 for 0-based indexing of node numbers.

• Efficient Insertion and Removal: Insertion and removal operations in heap trees are efficient. New elements are inserted at the next available position in the bottom-rightmost level, and the heap property is restored by comparing the element with its parent and swapping if necessary. Removal of the root element involves replacing it with the last element and heapifying down.

• Efficient Access to Extremal Elements: The minimum or maximum element is always at the root of the heap, allowing constant-time access.

Applications :

• Priority Queues: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(log N) time.

• Binomial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also in O(log N) time which is an O(N) operation in Binary Heap.

• Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array. You can see this gfg article to know more about the kth smallest or largest element.

Advantages of Heaps:

• Fast access to maximum/minimum element (O(1))

• Efficient Insertion and Deletion operations (O(log n)) Flexible size

• Can be efficiently implemented as an array

• Suitable for real-time applications

Disadvantages of Heaps:

• Not suitable for searching for an element other than maximum/minimum (O(n) in worst case)

• Extra memory overhead to maintain heap structure

• Slower than other data structures like arrays and linked lists for non-priority queue operations.

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

  getLeftChildIndex(parentIndex) {
    return 2 * parentIndex + 1;
  }

  getRightChildIndex(parentIndex) {
    return 2 * parentIndex + 2;
  }

  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }

  hasParent(index) {
    return this.getParentIndex(index) >= 0;
  }

  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [
      this.heap[index2],
      this.heap[index1],
    ];
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let currentIndex = this.heap.length - 1;
    while (
      this.hasParent(currentIndex) &&
      this.heap[currentIndex] < this.heap[this.getParentIndex(currentIndex)]
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  removeMin() {
    if (this.heap.length === 0) {
      throw new Error("Heap is empty");
    }
    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return minValue;
  }

  heapifyDown() {
    let currentIndex = 0;
    while (this.getLeftChildIndex(currentIndex) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(currentIndex);
      if (
        this.getRightChildIndex(currentIndex) < this.heap.length &&
        this.heap[this.getRightChildIndex(currentIndex)] <
          this.heap[smallerChildIndex]
      ) {
        smallerChildIndex = this.getRightChildIndex(currentIndex);
      }

      if (this.heap[currentIndex] < this.heap[smallerChildIndex]) {
        break;
      } else {
        this.swap(currentIndex, smallerChildIndex);
      }

      currentIndex = smallerChildIndex;
    }
  }
}

const priorityQueue = new MinHeap();
priorityQueue.insert(10);
priorityQueue.insert(5);
priorityQueue.insert(20);
priorityQueue.insert(3);

console.log("Removed min value:", priorityQueue.removeMin());
console.log("Removed min value:", priorityQueue.removeMin());