The Heap Space

Time Complexity - O(nlogn) We use min-heap if we want to sort in ascending order and max heap if we want to sort in descending order. We insert one by one into the heap, heapifying  from bottom to top while inserting in order to maintain corresponding heap property. Now, after all elements are insered into the heap, we extract elements one by one. Remember- we can only extract the root of a heap.  Also, after extraction, we put the last element in the level order traversal of heap as the new root and again heapify from top to bottom this time, in order to maintain the corresponding heap property. It is not a stable sort __________________________________________________________________________________________________________________________________________________________________ public class Main {     int[] heapArr;     int endOfHeap;          Main(int size){         this.heapArr...

  public class Main {     // the array used to implement max heap     // left child index is [2*x]  and right child index is [(2*x)+1]  if 'x' is the index of parent in array 'arr'.     // Cell 0 is unused for the sake of mathemaical simplicity.     int arr[];     // variable to store the last used index of arr     int lastUsedIndex;       // creating heap using constuctor     // Time Complexity - O(1) , Space Complexity - O(n)     Main(int size){         this.arr = new int[size];         this.lastUsedIndex=0;     }       // method to initialize the arr with Integer.MIN_VALUE, when it is empty     public void initializeArray(){         if(this.lastUsedIndex==0){             for(int i=0;i<this.arr.length;i++){     ...

  public class Main {     // the array used to implement min heap     // left child index is [2*x]  and right child index is [(2*x)+1]  if 'x' is the index of parent in  // array 'arr'.     // Cell 0 is unused for the sake of mathematical simplicity.     int arr[];     // variable to store the last used index of arr     int lastUsedIndex;       // creating heap using constuctor     // Time Complexity - O(1) , Space Complexity - O(n)     Main(int size){         this.arr = new int[size];         this.lastUsedIndex=0;     }       // method to initialize the arr with Integer.MIN_VALUE, when it is empty     public void initializeArray(){         if(this.lastUsedIndex==0){             for(int i=0;i<this.arr.length;i++){  ...

#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue