Binary Heap -Min and Max heap using Typescript

Binary heap

The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.[2]

A heap implemented with a binary tree that follows the following two rules:

  • Each node’s Element is greater than or equal to the elements of that node’s children…
  • The tree is a complete binary tree.

How heap store the data

Heaps, like binary search trees, do not use pointers to store their children. The heap stored item in the array, but its operations are more easily understood by looking at the binary tree representation. There is no ambiguity in the mapping between the array representation and the binary tree representation. To obtain the array, you can traverse the tree in level order.

We will discuss the prevalent data structure MinHeap. Minheap is also used to implement a priority queue. There are two types of heap.

  • MinHeap - It stores the min value at the root
  • MaxHeap- It stores the max value at the root

In this blog, we will discuss how to implement min heap in typescript(javascript). Many languages provide heap implementation in their framework, but some does not have inbuilt heaps in their frameworks like C# and JavaScript.

Adding Element to heap

We want to insert a node with value 01 to the heap on the left.

Extract Min Element

export class MinHeap {
  private items: Array<number>;
  constructor() {
    this.items = [];
  }
  public add(item: number) {
    this.items.push(item);
    this.heapifyUp(this.items.length - 1);
  }
  public extractMin() {
    if (this.count > 0) {
      let item = this.items[0];
      this.items[0] = this.items.pop();
      this.heapifyDown(0);
      return item;
    }
    return Infinity;
  }
  public get count() {
    return this.items.length;
  }
  private heapifyUp(index: number) {
    let parent = this.parent(index);
    if (parent >= 0 && this.items[parent] > this.items[index]) {
      this.swap(this.items, parent, index);
      this.heapifyUp(parent);
    }
  }
  private heapifyDown(index: number) {
    let smallest = index;
    let leftChild = this.letChild(index);
    let rightChild = this.rightChild(index);
    if (leftChild < this.count && this.items[leftChild] < this.items[index]) {
      smallest = leftChild;
    }
    if (
      rightChild < this.count &&
      this.items[rightChild] < this.items[smallest]
    ) {
      smallest = rightChild;
    }
    if (smallest != index) {
      this.swap(this.items, index, smallest);
      this.heapifyDown(smallest);
    }
  }
  private parent(index: number): number {
    if (index < 0) return -1;
    return Math.floor((index - 1) / 2);
  }
  private letChild(index: number) {
    if (index > 0) {
      return Math.floor((2 * index + 1) / 2);
    }
    return undefined;
  }
  private rightChild(index: number) {
    if (index > 0) {
      return Math.floor((2 * index + 2) / 2);
    }
    return undefined;
  }
  private swap(arr: Array<number>, i: number, j: number) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

Interview Questions

  1. Find kth smallest Element in an array
  2. Return kth largest Element in a stream
  3. Huffman Coding Compression Algorithm
  4. Heap Sort Algorithm

Please do not post any spam link in the comment box😊

Post a Comment (0)
Previous Post Next Post