A Heap is a specialized tree-based data structure that is used to efficiently manage and organize a collection of elements. It is a complete binary tree where each node has a value greater than or equal to its children (in a max heap) or less than or equal to its children (in a min heap). The root node of the heap always contains the highest (or lowest) value in the heap, making it useful for implementing priority queues and sorting algorithms. Heaps can be implemented using arrays or linked lists and have a time complexity of O(log n) for insertion, deletion, and search operations. Keep reading below to learn how to use a Heap in Javascript.
Looking to get a head start on your next software interview? Pickup a copy of the best book to prepare: Cracking The Coding Interview!
How to use a Heap in Javascript with example code
A heap is a data structure that is commonly used in computer science. It is a binary tree that satisfies the heap property. The heap property states that for every node in the tree, the value of the node is greater than or equal to the values of its children. In JavaScript, heaps can be implemented using arrays.
To create a heap in JavaScript, we can use the following code:
class Heap {
constructor() {
this.heap = [];
}
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex] > this.heap[index]) {
break;
}
let temp = this.heap[parentIndex];
this.heap[parentIndex] = this.heap[index];
this.heap[index] = temp;
index = parentIndex;
}
}
extractMax() {
let max = this.heap[0];
this.heap[0] = this.heap.pop();
this.sinkDown(0);
return max;
}
sinkDown(index) {
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let swapIndex = null;
if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[index]) {
swapIndex = leftChildIndex;
}
if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[index]) {
if (swapIndex === null || this.heap[rightChildIndex] > this.heap[swapIndex]) {
swapIndex = rightChildIndex;
}
}
if (swapIndex === null) {
break;
}
let temp = this.heap[index];
this.heap[index] = this.heap[swapIndex];
this.heap[swapIndex] = temp;
index = swapIndex;
}
}
}
In this code, we define a class called Heap that has three methods: insert, extractMax, and sinkDown. The insert method adds a new value to the heap and then calls the bubbleUp method to ensure that the heap property is maintained. The extractMax method removes the maximum value from the heap and then calls the sinkDown method to ensure that the heap property is maintained. The sinkDown method swaps the current node with its largest child until the heap property is satisfied.
To use the Heap class, we can create a new instance of it and then call its methods. For example:
let heap = new Heap();
heap.insert(5);
heap.insert(10);
heap.insert(3);
console.log(heap.extractMax()); // Output: 10
In this example, we create a new heap, insert three values into it, and then extract the maximum value. The output of this code is 10, which is the largest value in the heap.
What is a Heap in Javascript?
In conclusion, a Heap is a data structure that is commonly used in computer science and programming. In JavaScript, a Heap is a type of binary tree that is used to store and organize data in a specific way. It is particularly useful for sorting and searching large amounts of data quickly and efficiently. By understanding the basics of how a Heap works, developers can improve their programming skills and create more efficient and effective code. Whether you are a beginner or an experienced programmer, learning about Heaps in JavaScript is a valuable skill that can help you to solve complex problems and build better applications.
Elevate your software skills
Ergonomic Mouse |
Custom Keyboard |
SW Architecture |
Clean Code |
