DSA
JavaScript
Tree
Heap

#### What is a Heap Tree

A heap is a special type of tree-based data structure that satisfies the heap property: the value of each node is always greater than or equal to the value of its parent, with the exception of the root node, which has no parent. There are two types of heaps: min heaps and max heaps. In a min heap, the value of each node is always greater than or equal to the value of its parent, while in a max heap, the value of each node is always less than or equal to the value of its parent.

Heaps are typically implemented using an array, where the parent and child nodes of each node are found using the following formulas:

• The index of the left child of a node at index i is 2 * i + 1
• The index of the right child of a node at index i is 2 * i + 2
• The index of the parent of a node at index i is (i - 1) / 2

For example, consider the following min heap:

This heap can be represented as a Max Heap array as follows: `[20,12,18,8,11,7,5]` This heap can be represented as a Min Heap array as follows: `[5,11,7,20,18,12,8]`

To insert a new element into a heap, we first add it to the end of the array and then percolate it up the heap until it is in the correct position. To do this, we compare the value of the new element with the value of its parent and swap them if necessary. This process is repeated until the heap property is satisfied.

To remove the minimum (or maximum) element from a min (or max) heap, we remove the root node and replace it with the last element in the array. We then percolate this element down the heap until it is in the correct position. To do this, we compare the value of the element with the values of its children and swap it with the smaller (or larger) child if necessary. This process is repeated until the heap property is satisfied.

Heaps are commonly used for implementing priority queues, where the priority of each element is represented by its value in the heap. They are also used in algorithms for sorting and searching data, such as heap sort and Dijkstra’s algorithm.

Overall, heaps are a useful data structure for efficiently storing and manipulating data in a tree-like structure, and they have many practical applications in computer science.

Here is an example implementation of a min heap class in JavaScript:

``````class MinHeap {
constructor() {
this.heap = []
}

getParentIndex(index) {
return Math.floor((index - 1) / 2)
}

getLeftChildIndex(index) {
return 2 * index + 1
}

getRightChildIndex(index) {
return 2 * index + 2
}

hasParent(index) {
return this.getParentIndex(index) >= 0
}

hasLeftChild(index) {
return this.getLeftChildIndex(index) < this.heap.length
}

hasRightChild(index) {
return this.getRightChildIndex(index) < this.heap.length
}

getParent(index) {
return this.heap[this.getParentIndex(index)]
}

getLeftChild(index) {
return this.heap[this.getLeftChildIndex(index)]
}

getRightChild(index) {
return this.heap[this.getRightChildIndex(index)]
}

swap(index1, index2) {
const temp = this.heap[index1]
this.heap[index1] = this.heap[index2]
this.heap[index2] = temp
}

peek() {
if (this.heap.length === 0) {
throw new Error("Heap is empty")
}
return this.heap
}

poll() {
if (this.heap.length === 0) {
throw new Error("Heap is empty")
}
const item = this.heap
this.heap = this.heap[this.heap.length - 1]
this.heap.pop()
this.heapifyDown()
return item
}

this.heap.push(item)
this.heapifyUp()
}

heapifyUp() {
let index = this.heap.length - 1
while (this.hasParent(index) && this.getParent(index) > this.heap[index]) {
this.swap(this.getParentIndex(index), index)
index = this.getParentIndex(index)
}
}

heapifyDown() {
let index = 0
while (this.hasLeftChild(index)) {
let smallerChildIndex = this.getLeftChildIndex(index)
if (
this.hasRightChild(index) &&
this.getRightChild(index) < this.getLeftChild(index)
) {
smallerChildIndex = this.getRightChildIndex(index)
}
if (this.heap[index] < this.heap[smallerChildIndex]) {
break
}
this.swap(index, smallerChildIndex)
index = smallerChildIndex
}
}
}``````

Here is an example of how you can use the MinHeap class to create a min heap tree:

``````const heap = new MinHeap()

console.log(heap.heap) // [1, 5, 3, 8, 7, 9, 4]

1
/   \
5    3
/   \  /  \
8    7 9  4``````

To create a max heap, you can use the same class but change the comparison operator (<) in the heapifyDown function to > to ensure that the current node is swapped with the larger child. Hey there! This is Vishal Sharma. I reside and work at Gurgaon, India. I am a Software Engineer and primarily works with JavaScript, ReactJS and NodeJS. Welcome to my Javascript tech blog! Here, you'll find the latest news and updates in the world of Javascript, as well as tutorials and resources to help you improve your coding skills. From learning the basics of Javascript to advanced concepts like object-oriented programming, I post something for developers of all levels. Whether you're just starting out or you're a seasoned pro, you'll find valuable insights and information on our blog. So stay up-to-date with the latest in Javascript technology by bookmarking this page and checking back often.
Thank you for visiting!