Heap Sort


  • 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=new int[size];
        this.endOfHeap=0;
    }
    
    public void initializeHeapArr(){
        if(this.endOfHeap==0){
            for(int i=0;i<this.heapArr.length;i++){
                this.heapArr[i]=Integer.MIN_VALUE;
            }
        }
    }
    
    public void levelOrderTraversal(){
        if(this.endOfHeap==0){
            System.out.println("Heap is empty, can't traverse");
            return;
        }
        for(int i=1;i<=this.endOfHeap;i++){
            System.out.print(this.heapArr[i]+" ");
        }
        System.out.println();
    }
    
    public void insertIntoHeap(int data){
        if(this.endOfHeap==(this.heapArr.length-1)){
            System.out.println("Heap is full, can't insert '"+data+"'");
            return;
        }
        endOfHeap++;
        this.heapArr[this.endOfHeap]=data;
        
        // now heapify bottom to top
        
        // first we have to find its parent
        int currentParentIndex= -1; // if left children then parent index will be (children's index /2) and if right child (children's index -1 /2). In any case (children's index /2) will give us parent index as Java will round it off
        int currentChildIndex = this.endOfHeap;
        
        while(currentChildIndex>=1){
            currentParentIndex = currentChildIndex/2;
            if(this.heapArr[currentChildIndex]<this.heapArr[currentParentIndex]){
                // move up or swap
                int temp = this.heapArr[currentChildIndex];
                this.heapArr[currentChildIndex] = this.heapArr[currentParentIndex];
                this.heapArr[currentParentIndex]=temp;
            }
            else{
                break;
            }
            currentChildIndex = currentParentIndex;
        }
    }
    
    public int extractMinFromHeap(){
        if(this.endOfHeap==0){
            System.out.println("Can't extract node, as heap is empty");
            return Integer.MIN_VALUE;
        }
        int minValue = this.heapArr[1];
        
        // now make the last node in level order traversal of binary heap as the new root of binary heap
        this.heapArr[1]=this.heapArr[this.endOfHeap];
        // now delete the last node, as we have promoted it to be the new root
        this.heapArr[this.endOfHeap]=Integer.MIN_VALUE;
        this.endOfHeap--;
        
        
        // Now heapify from top to bottom
        int currentParentIndex=1;
        
        
        // find which child of the two is minimum, the child having the minimum value will become the candidate for swap if it has value less than root obviously
        while(currentParentIndex<this.endOfHeap){
            
            int currentChildIndex=-1;
            
            int leftChildIndex = 2*currentParentIndex;
            int rightChildIndex = (2*currentParentIndex)+1;
            
            int leftChildValue=Integer.MIN_VALUE;
            int rightChildValue = Integer.MIN_VALUE;
            
            if(leftChildIndex <= this.endOfHeap){
                leftChildValue=this.heapArr[leftChildIndex];
            }
            if(rightChildIndex <= this.endOfHeap){
                rightChildValue = this.heapArr[rightChildIndex];
            }
            
            // if no child is there
            if(leftChildValue==Integer.MIN_VALUE && rightChildValue== Integer.MIN_VALUE) {
            break;
            }
            // if left child is not there
            if(leftChildValue==Integer.MIN_VALUE && rightChildValue!= Integer.MIN_VALUE){
                currentChildIndex=rightChildIndex;
            }
            // if right child is not there
            else if(rightChildValue==Integer.MIN_VALUE && leftChildValue!=Integer.MIN_VALUE){
                currentChildIndex=leftChildIndex;
            }
            // if both child is present
            else{
                if(leftChildValue<=rightChildValue){
                    currentChildIndex = leftChildIndex;
                }
                else{
                    currentChildIndex = rightChildIndex;
                }
            }
            
            if(this.heapArr[currentParentIndex]>this.heapArr[currentChildIndex]){
                int temp = this.heapArr[currentParentIndex];
                this.heapArr[currentParentIndex]=this.heapArr[currentChildIndex];
                this.heapArr[currentChildIndex]=temp;
            }
            else{
                break;
            }
            currentParentIndex=currentChildIndex;
            
//            levelOrderTraversal();
        }
//        System.out.println();
        return minValue;
    }
    
    public static void main(String[] args) throws Exception {
        Main minHeap = new Main(15);
        minHeap.initializeHeapArr();
        minHeap.levelOrderTraversal();
        
        int[] arr={1,4,4,5,6,2,3,90,120,43,0};
        System.out.println("UnSorted Array :");
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        
        for(int i=0;i<arr.length;i++){
            minHeap.insertIntoHeap(arr[i]);
        }
        System.out.println();
        System.out.println("Min Heap initial Level order traversal...");
        minHeap.levelOrderTraversal();
        
        // System.out.println("extractMinFromHeap...");
        // System.out.println(minHeap.extractMinFromHeap());
        // System.out.println();
        // System.out.println("Level order traversal...");
        // minHeap.levelOrderTraversal();
        
        // for(int i=0;i<arr.length;i++){
        //     arr[i]=minHeap.extractMinFromHeap();
        // }
        
        System.out.println("Sorted Array :");
        for(int i=0;i<arr.length;i++){
            System.out.print(minHeap.extractMinFromHeap()+" ");
        }
    }
}


Output: 

Heap is empty, can't traverse
UnSorted Array :
1 4 4 5 6 2 3 90 120 43 0 
Min Heap initial Level order traversal...
0 1 2 5 4 4 3 90 120 43 6 
Sorted Array :
0 1 2 3 4 4 5 6 43 90 120

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#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
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can break this problem in
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array                 if(arr[j]>arr[j+1]){                     int temp = arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                 }             }             // after each iteration we ge
Read more