Max Heap in JavaScript
A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node. Mapping the elements of a heap into an array is trivial: if a node is stored at index k, then its left child is stored at index 2k + 1 and its right child at index 2k + 2.
How is Max Heap represented?
A-Max Heap is a Complete Binary Tree. A-Max heap is typically represented as an array. The root element will be at Arr[0]. Below table shows indexes of other nodes for the ith node, i.e., Arr[i]:
Arr[(i-1)/2] Returns the parent node.
Arr[(2*i)+1] Returns the left child node.
Arr[(2*i)+2] Returns the right child node.
Operations of Heap Data Structure:
- Heapify: a process of creating a heap from an array.
- Insertion: process to insert an element in existing heap time complexity O(log N).
- Deletion: deleting the top element of the heap or the highest priority element, and then organizing the heap and returning the element with time complexity O(log N).
- Peek: to check or find the most prior element in the heap, (max or min element for max and min heap).
Explanation: Now let us understand how the various helper methods maintain the order of the heap
- The helper methods like rightChild, leftChild, parent help us to get the element and its children at the specified index.
- The add() and remove() methods handle the insertion and deletion process
- The heapifyDown() method maintains the heap structure when an element is deleted.
- The heapifyUp() method maintains the heap structure when an element is added to the heap.
- The peek() method returns the root element of the heap and swap() method interchanges value at two nodes.
Example: In this example, we will implement the Max Heap data structure.
Javascript
class MaxHeap { constructor() { this .heap = []; } // Helper Methods getLeftChildIndex(parentIndex) { return 2 * parentIndex + 1; } getRightChildIndex(parentIndex) { return 2 * parentIndex + 2; } getParentIndex(childIndex) { return Math.floor((childIndex - 1) / 2); } hasLeftChild(index) { return this .getLeftChildIndex(index) < this .heap.length; } hasRightChild(index) { return this .getRightChildIndex(index) < this .heap.length; } hasParent(index) { return this .getParentIndex(index) >= 0; } leftChild(index) { return this .heap[ this .getLeftChildIndex(index)]; } rightChild(index) { return this .heap[ this .getRightChildIndex(index)]; } parent(index) { return this .heap[ this .getParentIndex(index)]; } swap(indexOne, indexTwo) { const temp = this .heap[indexOne]; this .heap[indexOne] = this .heap[indexTwo]; this .heap[indexTwo] = temp; } peek() { if ( this .heap.length === 0) { return null ; } return this .heap[0]; } // Removing an element will remove the // top element with highest priority then // heapifyDown will be called remove() { if ( this .heap.length === 0) { return null ; } const item = this .heap[0]; this .heap[0] = this .heap[ this .heap.length - 1]; this .heap.pop(); this .heapifyDown(); return item; } add(item) { this .heap.push(item); this .heapifyUp(); } heapifyUp() { let index = this .heap.length - 1; while ( this .hasParent(index) && this .parent(index) < this .heap[index]) { this .swap( this .getParentIndex(index), index); index = this .getParentIndex(index); } } heapifyDown() { let index = 0; while ( this .hasLeftChild(index)) { let largerChildIndex = this .getLeftChildIndex(index); if ( this .hasRightChild(index) && this .rightChild(index) > this .leftChild(index)) { largerChildIndex = this .getRightChildIndex(index); } if ( this .heap[index] > this .heap[largerChildIndex]) { break ; } else { this .swap(index, largerChildIndex); } index = largerChildIndex; } } printHeap() { var heap =` ${ this .heap[0]} ` for ( var i = 1; i< this .heap.length;i++) { heap += ` ${ this .heap[i]} `; } console.log(heap); } } // Creating the Heap var heap = new MaxHeap(); // Adding The Elements heap.add(10); heap.add(15); heap.add(30); heap.add(40); heap.add(50); heap.add(100); heap.add(40); // Printing the Heap heap.printHeap(); // Peeking And Removing Top Element console.log(heap.peek()); console.log(heap.remove()); // Printing the Heap // After Deletion. heap.printHeap(); |
100 40 50 10 30 15 40 100 100 50 40 40 10 30 15
Contact Us