The Heap Space

  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

  import java.util.*; // The node of the AVL tree // here we also maintain the height of each node so as to make height adjustments easier after  // the rotation in AVL tree class TreeNode{     int data;     int height;     TreeNode left;     TreeNode right;   // creating a node of AVL tree using constructor // Time Complexity - O(1) , Space Complexity - O(1)     TreeNode(int x){         this.data=x;         this.height=0;         this.left=null;         this.right=null;     }   } public class Main {   // Root of AVL tree     TreeNode root;   // Function to do a level order Traversal of AVL tree // Time Complexity - O(n) , Space Complexity - O(n) [As queue is used]    public void levelOrderTraversal() { //if AVL tree is empty   if (root == null) { ...

  Hence Algorithm of left rotating a node in AVL tree : treeNode leftRotate(cdn){ treeNode NR = cdn.right; cdn.right = NR.left; // any left child of NR will be right child of cdn NR.left = cdn; / / After doing rotation, we have to adjust the height of cdn and NR now cdn.height = calculateHeight(cdn); NR.height = calculateHeight(NR); // finally we will return newRoot to the recursively calling function return NR; } The algorithm of right rotate is just the mirror image of this : treeNode rightRotate(cdn){ treeNode NR = cdn.left; cdn.left= NR.right; // any right child of NR will be left child of cdn NR.right= cdn; / / After doing rotation, we have to adjust the height of cdn and NR now cdn.height = calculateHeight(cdn); NR.height = calculateHeight(NR); // finally we will return newRoot to the recursive...

  If a method returns some node instead of void, I am going to wrap that method like this : insert node function ->   public treeNode addNode(treeNode root, int data ) {                                                 .......................................................                                                  .......................................................                                                  ........................................................                                   ...

Insertion in Binary Search Tree : public treeNode insertNode(Node currentNode, int data) { if(currentNode==null){ currentNode = new treeNode(data); } // data moves to right subtree if(data> currentNode .data){ currentNode .right = insertNode( currentNode .right,data);  } //data moves to left subtree else if(data<= currentNode .data){ currentNode .left = insertNode( currentNode .left,data); } return currentNode ; } Deletion of a node in Binary Search Tree: public  treeNode deleteNode(treeNode node, int data){ if(root==null) // tree is empty return null; if(data<node.data){ node.left = deleteNode(node.left,data); } else if(data>root.data){ node.right = deleteNode(node.right,data); } // if the current node has the data to delete, consider three cases - 0/1/2 child of current node // if two child // find the minimum of the right subtree and replace the current no...