what is a heap in javascript
Poor Man
- Published
- Reading time
- 4 min read
- Length
- 590 words
On this page
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:
Text
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:
Text
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