Binary Heap - Min Heap - All Operations Implementation


 Click Me
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++){
                this.arr[i]=Integer.MIN_VALUE;
            }
        }
    }
 
    // method to add a new node to the binary min heap
    // Time Complexity - O(log n) , Space Complexity - O(1)
    public void addNode(int x){
        // if binary min heap is full
        if(this.lastUsedIndex==this.arr.length-1){
            System.out.println("Binary heap is full, can't add new node");
            return;
        }
        // else if binary min heap is empty
        this.lastUsedIndex++;
        this.arr[this.lastUsedIndex]=x;
     
        // heapify bottom to top
        heapifyBottomToTop();
    }
   
    // helper method to heapify from bottom node (newly added node) to top node. Heapify means swaping nodes to maintain the min heap property
    // Time Complexity - O(log n) , Space Complexity - O(1)
    private void heapifyBottomToTop(){ 

        // child node / newly added node's index
        int childNodeIndex = this.lastUsedIndex;

        // move from bottom to top , swaping nodes if needed to maintain the min heap property
        while(childNodeIndex>1){
         
            int parentNodeIndex = childNodeIndex/2;
         
            if(this.arr[parentNodeIndex]>this.arr[childNodeIndex]){
                int temp = this.arr[parentNodeIndex];
                this.arr[parentNodeIndex] = this.arr[childNodeIndex];
                this.arr[childNodeIndex] = temp;
            }
         
            childNodeIndex = parentNodeIndex;
        }
    }
 
    // method to do a level order traversal in binary heap
    // Time Complexity - O(n) , Space Complexity - O(1)
    public void levelOrderTraversal(){

        // if binary min heap is empty
        if(this.lastUsedIndex==0 || this.arr==null){
            System.out.println("Binary heap is empty, can't traverse");
            return;
        }
        // else if binary min heap is not empty
        System.out.println("Level Order Traversal...");
        for(int i=1;i<=this.lastUsedIndex;i++){
            System.out.print(this.arr[i]+" ");
        }
        System.out.println();
    }
 
 
    // method to extract the top node having minimum value from the binary min heap
    // we can only extract the root node from any heap. NO OTHER NODES CAN BE EXTRACTED.
    // Time Complexity - O(log n) , Space Complexity - O(1)
    public void extractMinFromHeap(){

         // if binary min heap is empty
        if(this.lastUsedIndex==0 || this.arr==null){
            System.out.println("Binary heap is empty, can't extract");
            return;
        }
        // else if binary min heap is not empty
        System.out.println("Extracted node from binary heap is: "+this.arr[1]);

        // copy data of ddepest node into the root node
        this.arr[1] = this.arr[this.lastUsedIndex];

        // delete the deepest node
        this.arr[this.lastUsedIndex] = Integer.MIN_VALUE;

        // update lastUsedIndex
        this.lastUsedIndex--;
     
        heapifyTopToBottom();
    }
 
    // helper method to heapify from top to bottom of heap. Done after extraction of node from any heap
    // Time Complexity - O(log n) , Space Complexity - O(1)
    private void heapifyTopToBottom(){

        // Start from the root node and move to the bottom, swapping nodes if needed to maintain the min-heap property
        int parentNodeIndex = 1;
     
        while(parentNodeIndex<this.lastUsedIndex){
            int childNodeIndex=-1;
         
            int leftChildIndex = 2*parentNodeIndex;
            int rightChildIndex = (2*parentNodeIndex)+1;
         
            // if current parent node has no child
            if(leftChildIndex>this.lastUsedIndex && rightChildIndex>this.lastUsedIndex){
                break;
            }
            // if current parent node has both child
            else if(leftChildIndex<=this.lastUsedIndex && rightChildIndex <= this.lastUsedIndex){
                if(this.arr[leftChildIndex]<=this.arr[rightChildIndex]){
                    childNodeIndex = leftChildIndex;
                }
                else{
                    childNodeIndex =  rightChildIndex;
                }
            }
            // else if current parent node has only left child
            else if(leftChildIndex<=this.lastUsedIndex && rightChildIndex>this.lastUsedIndex){
                childNodeIndex=leftChildIndex;
            }
            // else if current parent node has only right child
            else{
                childNodeIndex=rightChildIndex;
            }
         
            // now as we have childnode index, compare child with parent and swap if needed
            if(this.arr[childNodeIndex]<this.arr[parentNodeIndex]){
                int temp = this.arr[parentNodeIndex];
                this.arr[parentNodeIndex]=this.arr[childNodeIndex];
                this.arr[childNodeIndex]=temp;
            }
            parentNodeIndex = childNodeIndex;
        }
    }
 
    // wrapper method to do an inorder traversal on binary min heap - LEFT ROOT RIGHT
    // Time Complexity - O(n) , Space Complexity - O(n) [As recursion is used, so internal stack will be maintained]
    public void inOrderTraversal(){

         // if binary min heap is empty
        if(this.lastUsedIndex==0 || this.arr==null){
            System.out.println("Binary heap is empty, can't traverse");
            return;
        }
        // else if binary min heap is not empty
        System.out.println("Inorder Traversal...");
        inOrderTraversal(1);
        System.out.println();
    }
 
    // overloaded method to do inOrderTraversal recursively
    private void inOrderTraversal(int currentNodeIndex){
        if(currentNodeIndex>this.lastUsedIndex){
            return;
        }
        inOrderTraversal(2*currentNodeIndex);
        System.out.print(this.arr[currentNodeIndex]+" ");
        inOrderTraversal((2*currentNodeIndex)+1);
    }
 
    // wrapper method to do a preOrder traversal on binary min heap - ROOT LEFT RIGHT
    // Time Complexity - O(n) , Space Complexity - O(n) [As recursion is used, so internal stack will be maintained]
    public void preOrderTraversal(){

          // if binary min heap is empty
        if(this.lastUsedIndex==0 || this.arr==null){
            System.out.println("Binary heap is empty, can't traverse");
            return;
        }
        // else if binary min heap is not empty
        System.out.println("preOrder Traversal...");
        preOrderTraversal(1);
        System.out.println();
    }
 
     // overloaded method to do preOrderTraversal recursively
    private void preOrderTraversal(int currentNodeIndex){
         if(currentNodeIndex>this.lastUsedIndex){
            return;
        }
        System.out.print(this.arr[currentNodeIndex]+" ");
        preOrderTraversal(2*currentNodeIndex);
        preOrderTraversal((2*currentNodeIndex)+1);
    }
 
    // wrapper method to do a postOrder traversal on binary min heap - LEFT RIGHT ROOT 
    // Time Complexity - O(n) , Space Complexity - O(n) [As recursion is used, so internal stack will be maintained]
    public void postOrderTraversal(){

         // if binary min heap is empty
        if(this.lastUsedIndex==0 || this.arr==null){
            System.out.println("Binary heap is empty, can't traverse");
            return;
        }
         // else if binary min heap is not empty
        System.out.println("postOrder Traversal...");
        postOrderTraversal(1);
        System.out.println();
    }
 
    // overloaded method to do postOrderTraversal recursively
    private void postOrderTraversal(int currentNodeIndex){
         if(currentNodeIndex>this.lastUsedIndex){
            return;
        }
        postOrderTraversal(2*currentNodeIndex);
        postOrderTraversal((2*currentNodeIndex)+1);
        System.out.print(this.arr[currentNodeIndex]+" ");
    }
 
    // method to get the root node of binary min-heap, I am not returning the node here, just printing it
    // Time Complexity - O(1) , Space Complexity - O(1)
    public void peekBinaryHeap(){

         // if binary min heap is empty
         if(this.lastUsedIndex==0 || this.arr==null){
            System.out.println("Binary heap is empty, can't peek");
            return;
        }
        // else if binary min heap is not empty
        System.out.println("Root node of binary heap: "+this.arr[1]);
    }
 
    // method to delete complete binary min heap
    // Time Complexity - O(1) , Space Complexity - O(1)
    public void deleteCompleteBinaryHeap(){

        // if binary min heap is empty
        if(this.lastUsedIndex==0 || this.arr==null){
            System.out.println("Binary heap is empty, can't delete");
            return;
        }
        // else if binary min heap is not empty
        this.arr = null;
        this.lastUsedIndex=0;
        System.out.println("Binary heap deleted successfully");
    }
 
    public static void main(String[] args) throws Exception {
        Main binaryMinHeap = new Main(15);
        binaryMinHeap.initializeArray();
        binaryMinHeap.addNode(3);
        binaryMinHeap.addNode(5);
        binaryMinHeap.addNode(8);
        binaryMinHeap.addNode(17);
        binaryMinHeap.addNode(19);
        binaryMinHeap.addNode(36);
        binaryMinHeap.addNode(40);
        binaryMinHeap.addNode(25);
        binaryMinHeap.addNode(100);
        binaryMinHeap.addNode(1);
        binaryMinHeap.levelOrderTraversal();
        binaryMinHeap.extractMinFromHeap();
        binaryMinHeap.levelOrderTraversal();
        binaryMinHeap.extractMinFromHeap();
        binaryMinHeap.levelOrderTraversal();
        binaryMinHeap.inOrderTraversal();
        binaryMinHeap.preOrderTraversal();
        binaryMinHeap.postOrderTraversal();
        binaryMinHeap.peekBinaryHeap();
        binaryMinHeap.deleteCompleteBinaryHeap();
        binaryMinHeap.levelOrderTraversal();
        binaryMinHeap.deleteCompleteBinaryHeap();
     
    }
}
Output:

 
Level Order Traversal...
1 3 8 17 5 36 40 25 100 19 
Extracted node from binary heap is: 1
Level Order Traversal...
3 5 8 17 19 36 40 25 100 
Extracted node from binary heap is: 3
Level Order Traversal...
5 17 8 25 19 36 40 100 
Inorder Traversal...
100 25 17 19 5 36 8 40 
preOrder Traversal...
5 17 25 100 19 8 36 40 
postOrder Traversal...
100 25 19 17 36 40 8 5 
Root node of binary heap: 5
Binary heap deleted successfully
Binary heap is empty, can't traverse
Binary heap is empty, can't delete

Comments

Post a Comment

Popular posts from this blog

Quick Sort

According to me, it is the easiest and one of the most important and efficient sorting algorithm. Java 7 also uses quicksort for their .sort() method Time Complexity - O(nlogn) Space Complexity - O(n) -> As we are using recursion, it uses the internal stack In quicksort, we chose a pivot element first (in this program, I chose the last element as pivot) All the elements in any array, which are less than the pivot remains to the left of pivot and all the elements which are greater than the pivot element remains to the right of pivot. To do the above, we first chose last element as pivot element, i as (start-1) and j as start In quicksort, we only have to take care of pivot, i and j Now, we compare if a[i]<= pivot element. If yes, we increment i and swap arr[i] and arr[j] After completing one iteration from start to end, we get a pivot element fixed at its right position. Now, we recursively do this for the left subarray and right subarray to the pivot element. QuickS...
Read more

Disjoint Set - Implemented Using Arrays

Image
  What is a Disjoint Set? Well, Wikipedia has the perfect definition -  A disjoint-set data structure (also called a union-find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses, disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph. The disjoint set has mainly 3 Operations: makeset() -> makes 'n' number of disjoint sets containing single elements find(currentSet) -> returns the representative/parent of currentSet union(set1,set2) -> merges two disjoint sets represented by set1 and set2 into a new disjoint set.  Before going through code, I would recommend watching this video -  https://www.youtube.com/watch?v=wU6udHRIkcc Code: public class Mai...
Read more

Graph Traversal Code - BFS on Graph represented using Adjacency Matrix

Image
  import java.util.*; // A graph Node class GraphNode{     String name;     boolean isVisited;     //index is used to map this node with index of Adjacency Matrix     int index;      GraphNode(String name,int index){         this.name = name;         this.isVisited = false;         this.index = index;     }      } public class Main {          // A List to store the address of all the nodes of the graph     ArrayList<GraphNode> nodeList = new ArrayList<GraphNode>();     // An adjacency Matrix to store the details about which nodes are adjacent to each other (basically which two nodes has a edge between them)     int [][] adjacencyMatrix;          // Constructor     Main(ArrayList<GraphNode> nodeList){         this.nod...
Read more