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;
}
}