How does a heapsort work

In selection sort, a list is sorted in the following way. Initially there will be an empty sorted list and the un-sorted list. We select the first element(According to the sort order) from the unsorted list and add it to the sorted list. We select the second element and append it to the sorted list and so on until the entire list is sorted.

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);
}
}
}