Implementation of Heap Data Structure:-
The following code shows the implementation of a max-heap.
Let’s understand the maxHeapify function in detail:-
maxHeapify is the function responsible for restoring the property of the Max Heap. It arranges the node i, and its subtrees accordingly so that the heap property is maintained.
- Suppose we are given an array, arr[] representing the complete binary tree. The left and the right child of ith node are in indices 2*i+1 and 2*i+2.
- We set the index of the current element, i, as the ‘MAXIMUM’.
- If arr[2 * i + 1] > arr[i], i.e., the left child is larger than the current value, it is set as ‘MAXIMUM’.
- Similarly if arr[2 * i + 2] > arr[i], i.e., the right child is larger than the current value, it is set as ‘MAXIMUM’.
- Swap the ‘MAXIMUM’ with the current element.
- Repeat steps 2 to 5 till the property of the heap is restored.
C++
// C++ code to depict // the implementation of a max heap. #include <bits/stdc++.h> using namespace std; // A class for Max Heap. class MaxHeap { // A pointer pointing to the elements // in the array in the heap. int * arr; // Maximum possible size of // the Max Heap. int maxSize; // Number of elements in the // Max heap currently. int heapSize; public : // Constructor function. MaxHeap( int maxSize); // Heapifies a sub-tree taking the // given index as the root. void MaxHeapify( int ); // Returns the index of the parent // of the element at ith index. int parent( int i) { return (i - 1) / 2; } // Returns the index of the left child. int lChild( int i) { return (2 * i + 1); } // Returns the index of the // right child. int rChild( int i) { return (2 * i + 2); } // Removes the root which in this // case contains the maximum element. int removeMax(); // Increases the value of the key // given by index i to some new value. void increaseKey( int i, int newVal); // Returns the maximum key // (key at root) from max heap. int getMax() { return arr[0]; } int curSize() { return heapSize; } // Deletes a key at given index i. void deleteKey( int i); // Inserts a new key 'x' in the Max Heap. void insertKey( int x); }; // Constructor function builds a heap // from a given array a[] // of the specified size. MaxHeap::MaxHeap( int totSize) { heapSize = 0; maxSize = totSize; arr = new int [totSize]; } // Inserting a new key 'x'. void MaxHeap::insertKey( int x) { // To check whether the key // can be inserted or not. if (heapSize == maxSize) { cout << "\nOverflow: Could not insertKey\n" ; return ; } // The new key is initially // inserted at the end. heapSize++; int i = heapSize - 1; arr[i] = x; // The max heap property is checked // and if violation occurs, // it is restored. while (i != 0 && arr[parent(i)] < arr[i]) { swap(arr[i], arr[parent(i)]); i = parent(i); } } // Increases value of key at // index 'i' to new_val. void MaxHeap::increaseKey( int i, int newVal) { arr[i] = newVal; while (i != 0 && arr[parent(i)] < arr[i]) { swap(arr[i], arr[parent(i)]); i = parent(i); } } // To remove the root node which contains // the maximum element of the Max Heap. int MaxHeap::removeMax() { // Checking whether the heap array // is empty or not. if (heapSize <= 0) return INT_MIN; if (heapSize == 1) { heapSize--; return arr[0]; } // Storing the maximum element // to remove it. int root = arr[0]; arr[0] = arr[heapSize - 1]; heapSize--; // To restore the property // of the Max heap. MaxHeapify(0); return root; } // In order to delete a key // at a given index i. void MaxHeap::deleteKey( int i) { // It increases the value of the key // to infinity and then removes // the maximum value. increaseKey(i, INT_MAX); removeMax(); } // To heapify the subtree this method // is called recursively void MaxHeap::MaxHeapify( int i) { int l = lChild(i); int r = rChild(i); int largest = i; if (l < heapSize && arr[l] > arr[i]) largest = l; if (r < heapSize && arr[r] > arr[largest]) largest = r; if (largest != i) { swap(arr[i], arr[largest]); MaxHeapify(largest); } } // Driver program to test above functions. int main() { // Assuming the maximum size of the heap to be 15. MaxHeap h(15); // Asking the user to input the keys: int k, i, n = 6, arr[10]; cout << "Entered 6 keys:- 3, 10, 12, 8, 2, 14 \n" ; h.insertKey(3); h.insertKey(10); h.insertKey(12); h.insertKey(8); h.insertKey(2); h.insertKey(14); // Printing the current size // of the heap. cout << "The current size of the heap is " << h.curSize() << "\n" ; // Printing the root element which is // actually the maximum element. cout << "The current maximum element is " << h.getMax() << "\n" ; // Deleting key at index 2. h.deleteKey(2); // Printing the size of the heap // after deletion. cout << "The current size of the heap is " << h.curSize() << "\n" ; // Inserting 2 new keys into the heap. h.insertKey(15); h.insertKey(5); cout << "The current size of the heap is " << h.curSize() << "\n" ; cout << "The current maximum element is " << h.getMax() << "\n" ; return 0; } |
Java
// Java code to depict // the implementation of a max heap. import java.util.Arrays; import java.util.Scanner; public class MaxHeap { // A pointer pointing to the elements // in the array in the heap. int [] arr; // Maximum possible size of // the Max Heap. int maxSize; // Number of elements in the // Max heap currently. int heapSize; // Constructor function. MaxHeap( int maxSize) { this .maxSize = maxSize; arr = new int [maxSize]; heapSize = 0 ; } // Heapifies a sub-tree taking the // given index as the root. void MaxHeapify( int i) { int l = lChild(i); int r = rChild(i); int largest = i; if (l < heapSize && arr[l] > arr[i]) largest = l; if (r < heapSize && arr[r] > arr[largest]) largest = r; if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; MaxHeapify(largest); } } // Returns the index of the parent // of the element at ith index. int parent( int i) { return (i - 1 ) / 2 ; } // Returns the index of the left child. int lChild( int i) { return ( 2 * i + 1 ); } // Returns the index of the // right child. int rChild( int i) { return ( 2 * i + 2 ); } // Removes the root which in this // case contains the maximum element. int removeMax() { // Checking whether the heap array // is empty or not. if (heapSize <= 0 ) return Integer.MIN_VALUE; if (heapSize == 1 ) { heapSize--; return arr[ 0 ]; } // Storing the maximum element // to remove it. int root = arr[ 0 ]; arr[ 0 ] = arr[heapSize - 1 ]; heapSize--; // To restore the property // of the Max heap. MaxHeapify( 0 ); return root; } // Increases value of key at // index 'i' to new_val. void increaseKey( int i, int newVal) { arr[i] = newVal; while (i != 0 && arr[parent(i)] < arr[i]) { int temp = arr[i]; arr[i] = arr[parent(i)]; arr[parent(i)] = temp; i = parent(i); } } // Returns the maximum key // (key at root) from max heap. int getMax() { return arr[ 0 ]; } int curSize() { return heapSize; } // Deletes a key at given index i. void deleteKey( int i) { // It increases the value of the key // to infinity and then removes // the maximum value. increaseKey(i, Integer.MAX_VALUE); removeMax(); } // Inserts a new key 'x' in the Max Heap. void insertKey( int x) { // To check whether the key // can be inserted or not. if (heapSize == maxSize) { System.out.println( "\nOverflow: Could not insertKey\n" ); return ; } // The new key is initially // inserted at the end. heapSize++; int i = heapSize - 1 ; arr[i] = x; // The max heap property is checked // and if violation occurs, // it is restored. while (i != 0 && arr[parent(i)] < arr[i]) { int temp = arr[i]; arr[i] = arr[parent(i)]; arr[parent(i)] = temp; i = parent(i); } } // Driver program to test above functions. public static void main(String[] args) { // Assuming the maximum size of the heap to be 15. MaxHeap h = new MaxHeap( 15 ); // Asking the user to input the keys: int k, i, n = 6 ; System.out.println( "Entered 6 keys:- 3, 10, 12, 8, 2, 14 \n" ); h.insertKey( 3 ); h.insertKey( 10 ); h.insertKey( 12 ); h.insertKey( 8 ); h.insertKey( 2 ); h.insertKey( 14 ); // Printing the current size // of the heap. System.out.println( "The current size of the heap is " + h.curSize() + "\n" ); // Printing the root element which is // actually the maximum element. System.out.println( "The current maximum element is " + h.getMax() + "\n" ); // Deleting key at index 2. h.deleteKey( 2 ); // Printing the size of the heap // after deletion. System.out.println( "The current size of the heap is " + h.curSize() + "\n" ); // Inserting 2 new keys into the heap. h.insertKey( 15 ); h.insertKey( 5 ); System.out.println( "The current size of the heap is " + h.curSize() + "\n" ); System.out.println( "The current maximum element is " + h.getMax() + "\n" ); } } |
Python3
# Python code to depict # the implementation of a max heap. class MaxHeap: # A pointer pointing to the elements # in the array in the heap. arr = [] # Maximum possible size of # the Max Heap. maxSize = 0 # Number of elements in the # Max heap currently. heapSize = 0 # Constructor function. def __init__( self , maxSize): self .maxSize = maxSize self .arr = [ None ] * maxSize self .heapSize = 0 # Heapifies a sub-tree taking the # given index as the root. def MaxHeapify( self , i): l = self .lChild(i) r = self .rChild(i) largest = i if l < self .heapSize and self .arr[l] > self .arr[i]: largest = l if r < self .heapSize and self .arr[r] > self .arr[largest]: largest = r if largest ! = i: temp = self .arr[i] self .arr[i] = self .arr[largest] self .arr[largest] = temp self .MaxHeapify(largest) # Returns the index of the parent # of the element at ith index. def parent( self , i): return (i - 1 ) / / 2 # Returns the index of the left child. def lChild( self , i): return ( 2 * i + 1 ) # Returns the index of the # right child. def rChild( self , i): return ( 2 * i + 2 ) # Removes the root which in this # case contains the maximum element. def removeMax( self ): # Checking whether the heap array # is empty or not. if self .heapSize < = 0 : return None if self .heapSize = = 1 : self .heapSize - = 1 return self .arr[ 0 ] # Storing the maximum element # to remove it. root = self .arr[ 0 ] self .arr[ 0 ] = self .arr[ self .heapSize - 1 ] self .heapSize - = 1 # To restore the property # of the Max heap. self .MaxHeapify( 0 ) return root # Increases value of key at # index 'i' to new_val. def increaseKey( self , i, newVal): self .arr[i] = newVal while i ! = 0 and self .arr[ self .parent(i)] < self .arr[i]: temp = self .arr[i] self .arr[i] = self .arr[ self .parent(i)] self .arr[ self .parent(i)] = temp i = self .parent(i) # Returns the maximum key # (key at root) from max heap. def getMax( self ): return self .arr[ 0 ] def curSize( self ): return self .heapSize # Deletes a key at given index i. def deleteKey( self , i): # It increases the value of the key # to infinity and then removes # the maximum value. self .increaseKey(i, float ( "inf" )) self .removeMax() # Inserts a new key 'x' in the Max Heap. def insertKey( self , x): # To check whether the key # can be inserted or not. if self .heapSize = = self .maxSize: print ( "\nOverflow: Could not insertKey\n" ) return # The new key is initially # inserted at the end. self .heapSize + = 1 i = self .heapSize - 1 self .arr[i] = x # The max heap property is checked # and if violation occurs, # it is restored. while i ! = 0 and self .arr[ self .parent(i)] < self .arr[i]: temp = self .arr[i] self .arr[i] = self .arr[ self .parent(i)] self .arr[ self .parent(i)] = temp i = self .parent(i) # Driver program to test above functions. if __name__ = = '__main__' : # Assuming the maximum size of the heap to be 15. h = MaxHeap( 15 ) # Asking the user to input the keys: k, i, n = 6 , 0 , 6 print ( "Entered 6 keys:- 3, 10, 12, 8, 2, 14 \n" ) h.insertKey( 3 ) h.insertKey( 10 ) h.insertKey( 12 ) h.insertKey( 8 ) h.insertKey( 2 ) h.insertKey( 14 ) # Printing the current size # of the heap. print ( "The current size of the heap is " + str (h.curSize()) + "\n" ) # Printing the root element which is # actually the maximum element. print ( "The current maximum element is " + str (h.getMax()) + "\n" ) # Deleting key at index 2. h.deleteKey( 2 ) # Printing the size of the heap # after deletion. print ( "The current size of the heap is " + str (h.curSize()) + "\n" ) # Inserting 2 new keys into the heap. h.insertKey( 15 ) h.insertKey( 5 ) print ( "The current size of the heap is " + str (h.curSize()) + "\n" ) print ( "The current maximum element is " + str (h.getMax()) + "\n" ) |
Javascript
// JavaScript code to depict // the implementation of a max heap. class MaxHeap { constructor(maxSize) { // the array in the heap. this .arr = new Array(maxSize).fill( null ); // Maximum possible size of // the Max Heap. this .maxSize = maxSize; // Number of elements in the // Max heap currently. this .heapSize = 0; } // Heapifies a sub-tree taking the // given index as the root. MaxHeapify(i) { const l = this .lChild(i); const r = this .rChild(i); let largest = i; if (l < this .heapSize && this .arr[l] > this .arr[i]) { largest = l; } if (r < this .heapSize && this .arr[r] > this .arr[largest]) { largest = r; } if (largest !== i) { const temp = this .arr[i]; this .arr[i] = this .arr[largest]; this .arr[largest] = temp; this .MaxHeapify(largest); } } // Returns the index of the parent // of the element at ith index. parent(i) { return Math.floor((i - 1) / 2); } // Returns the index of the left child. lChild(i) { return 2 * i + 1; } // Returns the index of the // right child. rChild(i) { return 2 * i + 2; } // Removes the root which in this // case contains the maximum element. removeMax() { // Checking whether the heap array // is empty or not. if ( this .heapSize <= 0) { return null ; } if ( this .heapSize === 1) { this .heapSize -= 1; return this .arr[0]; } // Storing the maximum element // to remove it. const root = this .arr[0]; this .arr[0] = this .arr[ this .heapSize - 1]; this .heapSize -= 1; // To restore the property // of the Max heap. this .MaxHeapify(0); return root; } // Increases value of key at // index 'i' to new_val. increaseKey(i, newVal) { this .arr[i] = newVal; while (i !== 0 && this .arr[ this .parent(i)] < this .arr[i]) { const temp = this .arr[i]; this .arr[i] = this .arr[ this .parent(i)]; this .arr[ this .parent(i)] = temp; i = this .parent(i); } } // Returns the maximum key // (key at root) from max heap. getMax() { return this .arr[0]; } curSize() { return this .heapSize; } // Deletes a key at given index i. deleteKey(i) { // It increases the value of the key // to infinity and then removes // the maximum value. this .increaseKey(i, Infinity); this .removeMax(); } // Inserts a new key 'x' in the Max Heap. insertKey(x) { // To check whether the key // can be inserted or not. if ( this .heapSize === this .maxSize) { console.log( "\nOverflow: Could not insertKey\n" ); return ; } let i = this .heapSize; this .arr[i] = x; // The new key is initially // inserted at the end. this .heapSize += 1; // The max heap property is checked // and if violation occurs, // it is restored. while (i !== 0 && this .arr[ this .parent(i)] < this .arr[i]) { const temp = this .arr[i]; this .arr[i] = this .arr[ this .parent(i)]; this .arr[ this .parent(i)] = temp; i = this .parent(i); } } } // Driver program to test above functions. // Assuming the maximum size of the heap to be 15. const h = new MaxHeap(15); // Asking the user to input the keys: console.log( "Entered 6 keys:- 3, 10, 12, 8, 2, 14 \n" ); h.insertKey(3); h.insertKey(10); h.insertKey(12); h.insertKey(8); h.insertKey(2); h.insertKey(14); // Printing the current size // of the heap. console.log( "The current size of the heap is " + h.curSize() + "\n" ); // Printing the root element which is // actually the maximum element. console.log( "The current maximum element is " + h.getMax() + "\n" ); // Deleting key at index 2. h.deleteKey(2); // Printing the size of the heap // after deletion. console.log( "The current size of the heap is " + h.curSize() + "\n" ); // Inserting 2 new keys into the heap. h.insertKey(15); h.insertKey(5); console.log( "The current size of the heap is " + h.curSize() + "\n" ); console.log( "The current maximum element is " + h.getMax() + "\n" ); // Contributed by sdeadityasharma |
Output
Entered 6 keys:- 3, 10, 12, 8, 2, 14 The current size of the heap is 6 The current maximum element is 14 The current size of the heap is 5 The current size of the heap is 7 The current maximum element is 15
Contact Us