Heap sort

Heap sort is a comparison-based sorting algorithm and divides the input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

Heap sort is not stable sorting. A heap sort is especially efficient for data that is already stored in a binary tree. Heap sort does not take any extra space.

Write a program to implement heap sort.

source Code

package com.dsacode.Algorithm.sorting;
 
public class HeapSort {
    private int heapsize;
    public HeapSort(){
        heapsize =0;
    }
     
    int left(int i){
        return (2*i);
    }
 
    int right(int i){
        return (2*i+1);
    }
 
    int parent(int i){
        return (i/2);
    }
 
    void MaxHeapify(int A[], int i){
         
    int largest,temp,l,r;
     
    l=left(i);
    r=right(i);
 
    if( A[l] > A[i] && l <= heapsize)
        largest=l;
    else
        largest=i;
     
    if( A[r] > A[largest] && r <= heapsize)
        largest=r;
 
    if(largest!=i){
        temp=A[i];
        A[i]=A[largest];
        A[largest]=temp;
        MaxHeapify(A,largest);
        }
    }
 
    void buildmaxheap(int A[], int n){
        heapsize=n;
        for(int i=n/2; i>=1;i--)
            MaxHeapify(A,i);
    }
 
    void heapsort(int A[], int n){
        int temp;
        buildmaxheap(A,n);
        for(int i=n;i>=2;i--){
            temp=A[i];
            A[i]=A[1];
            A[1]=temp;
         
            heapsize--;
            MaxHeapify(A,1);
        }
    }
     
    public static void main(String[] args) {
         
          int []arr=new int[20];
          arr[1]=12;
          arr[2]=34;
          arr[3]=56;
          arr[4]=23;
          arr[5]=45;
          arr[6]=78;
          arr[7]=99;
           
          System.out.print("Unsorted array before sorting : [" );
          for(int i=1; i <= 7; i++){
              if(i==7)
                  System.out.print(arr[i] +"]");
              else
                  System.out.print(arr[i] +",");
          }
          System.out.println();
           
          HeapSort obj = new HeapSort();
          obj.heapsort(arr,7);
           
          System.out.print("Sorted array After Heap sorting :[");
          for(int i = 1; i <= 7; i++){
              if(i == 7)
                  System.out.print(arr[i] +"]");
              else
                  System.out.print(arr[i] +",");
            }
          }
}
  

Output

Unsorted array before sorting: [12, 34, 56, 23, 45, 78, 99]
Sorted array After Heap sorting: [12, 23, 34, 45, 56, 78, 99]

Algorithm Explanation

	Construct a heap using the array of elements.
	Add each item to heap and MaxHeapify when inserting into the heap.
	When all items have been added, remove them one by one. The topmost item is stored in an array.
	Sorted elements stored in an array.

Time Complexity

Reference

1. https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
2. http://en.wikipedia.org/wiki/Heapsort
3. http://www.stoimen.com/blog/2012/08/07/computer-algorithms-heap-and-heapsort-data-structure/