what is a heap in javascript

What is a Heap in JavaScript?

As a blogger, I have come across the term "Heap" in JavaScript while working on a project. A heap is a data structure, similar to an array or a linked list, that stores data in a particular way for efficient retrieval. In a heap, the elements are stored in a way that they follow a particular order. This order could be ascending or descending, depending on the requirement of the program.

A heap is also known as a binary heap because it is implemented using a binary tree. A binary tree is a tree data structure in which each node has at most two child nodes, referred to as the left child and the right child.

Two Types of Heap

• Max Heap: In a Max Heap, the parent node is always greater than or equal to its child nodes.
• Min Heap: In a Min Heap, the parent node is always less than or equal to its child nodes.

How to Implement Heap in JavaScript?

There are multiple ways to implement a heap in JavaScript:

• Array Implementation: This is the simplest way to implement a heap in JavaScript. In this implementation, we use an array to store the elements of the heap. The root element of the heap is stored at index 0 of the array. The left child of any element at index i is stored at index 2i + 1, and the right child is stored at index 2i + 2. The parent of any element at index i is stored at index Math.floor((i-1)/2). Here is the code for implementing a Max Heap using an array:

let arr = [];

function insert(element) {
    arr.push(element);
    let index = arr.length - 1;
    while (index > 0 && arr[index] > arr[Math.floor((index-1)/2)]) {
        [arr[index], arr[Math.floor((index-1)/2)]] = [arr[Math.floor((index-1)/2)], arr[index]];
        index = Math.floor((index-1)/2);
    }
}

insert(10); // [10]
insert(20); // [20, 10]
insert(15); // [20, 10, 15]
insert(30); // [30, 20, 15, 10]
        

• Priority Queue: A Priority Queue is a data structure that is used to store items with associated priorities. In a Priority Queue, the element with the highest priority is always dequeued first. A Priority Queue can be implemented using a heap. Here is the code for implementing a Priority Queue using a Max Heap:

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

  insert(element, priority) {
    let node = {value: element, priority: priority};
    this.heap.push(node);
    let index = this.heap.length - 1;
    while (index > 0 && this.heap[index].priority > this.heap[Math.floor((index-1)/2)].priority) {
        [this.heap[index], this.heap[Math.floor((index-1)/2)]] = [this.heap[Math.floor((index-1)/2)], this.heap[index]];
        index = Math.floor((index-1)/2);
    }
  }

  remove() {
    if (this.heap.length === 0) {
        return null;
    }
    let node = this.heap[0];
    let last = this.heap.pop();
    if (this.heap.length > 0) {
        this.heap[0] = last;
        let index = 0;
        while (true) {
            let left = 2*index + 1;
            let right = 2*index + 2;
            let largest = index;
            if (left < this.heap.length && this.heap[left].priority > this.heap[largest].priority) {
                largest = left;
            }
            if (right < this.heap.length && this.heap[right].priority > this.heap[largest].priority) {
                largest = right;
            }
            if (largest === index) {
                break;
            }
            [this.heap[largest], this.heap[index]] = [this.heap[index], this.heap[largest]];
            index = largest;
        }
    }
    return node.value;
  }
}

let pq = new PriorityQueue();
pq.insert("A", 2);
pq.insert("B", 3);
pq.insert("C", 1);
pq.insert("D", 4);
console.log(pq.remove()); // D
console.log(pq.remove()); // B
console.log(pq.remove()); // A
console.log(pq.remove()); // C
console.log(pq.remove()); // null