How does a heapsort work

Heapsort also works in the similar fashion. In heapsort, ‘Heap’ datastructure is used to maintain the unsorted list and hence the name heapsort. A heap is an array-based data structure visualized as a complete binary tree.
For example let us consider the following array and its corresponding binary tree form

Index  0  1   2  3  4  5  6
Array: 7  6   5  1  3  2  4  

                                                 7
                    / 
                  6      5
                 /     /
                1   3  2   4

array[0] contains the root element, and array[2*0+1] contains the left child and array[2*0+2] contains the right child. In general ith node has its left and right children at 2*i+1 and 2*i+2 indices respectively and the parent of ith node will be at array[i/2].

The above heap is also a max-heap in which data at every node is greater than those of its children.

In this algorithm, all the elements are formed into a max-heap by repeatedly using heapify procedure. heapify procedure works on any node which violates the max-heap property. for example let us consider the following heap is not a max-heap because 2 is less than it’s children.
                       2—–> violation
               /
              6   5
             /
            1  4
to correct this we will swap 2 and 6 ( bigger child) and recursively apply the same procedure for the node 2.
                               6
                    /
  violation  <—- 2   5   
                  /
                 1   4
So the following heap is a max-heap now.
         6
     /
    4   5
   /
  1   2
The build heap procedure scans through all the non-leaf nodes and calls the heapify procedure.

Finally the heap contains the maximum element at the root of the heap ( array[0] ). To sort the array. We swap the root element with the end element (array[length-1]). Now the heap may violate the max heap property at the root node. so call the heapify procedure. Next time we can exclude the last element because it is it’s correct place. The heap size is reduced by one.

The following Java Program implements the above algorithm.

import java.util.Scanner;
public class Main {
    public static void main(String[] args)
    {
        Scanner reader = new Scanner(System.in);
        int N = Integer.parseInt(reader.nextLine());
        int []array = new int[N];
        int i;
        for( i = 0 ; i < N ; i++)
        {
            array[i] = reader.nextInt();
        }
        heapSort(array);
        //display the sorted array
        for( i = 0 ; i < N ; i++)
        {
            System.out.print(array[i] + " ");
        }
    }
    public static void heapSort(int[] array)
    {
        //build the max heap
        buildHeap( array );

        int i;
        for ( i = array.length-1 ; i > 0 ; i--)
        {
            //swap the max element to the end of the array
            int t = array[0];
            array[0] = array[i];
            array[i] = t;
            //heapify since max is removed
            heapify( array, 0, i);
        }

    }
    public static void buildHeap(int[] array)
    {
        if( array.length > 1)
        {
            int i;
            //heapify procedure is called only for half of the elems
            //because remaining are leaves and don't need to be adjusted
            for( i = array.length / 2 ; i >= 0 ; i--)
            {
                heapify(array, i, array.length);
            }
        }
    }
    public static void heapify(int[] array, int ind, int size)
    {
       if( ind >= size/2)
           return;

       int leftInd = 2*ind+1;
       int rightInd = 2*ind+2;
       int swapInd = leftInd;  //initialize swapInd to the left child
       //If right child is there, check if it needs to be swapped
       if( rightInd < size && array[leftInd] < array[rightInd])
           swapInd = rightInd;

       //check if swapping is required
       if( array[ind] < array[swapInd])
       {
           //swap parent and child
           int temp = array[ind];
           array[ind] = array[swapInd];
           array[swapInd] = temp;
           //recursive call on swapped index
           heapify(array,swapInd,size);
       }
    }
}