HeapSort in Java

Heap Sort sorts an array in place with time complexity O(N log N). Following is the code to do the same

Binary Heap

A binary heap has two following two properties

1. Structural property : All levels except the last are full. Last level is left filled.
2. Heap property : Priority of node is at least as large as it's parent (This is true for min heap but similarly you can have max heap where priority of parent is at least as large as it's children)

Code :

package Sorts;

import java.util.Arrays;

/**
 * Created by Aniket on 3/3/14.
 */
public class HeapSort {

    public int getLeft(int i){
        return 2*i;
    }

    public int getRight(int i){
        return 2*i+1;
    }

    public int getParent(int i){
        return i/2;
    }

    public void maxHeapify(int[]  array, int position){

        int leftPosition = getLeft(position);
        int rightPosition = getRight(position);

        int largest = 0;

        if(leftPosition <= array.length && array[leftPosition-1] > array[position-1]){
            largest = leftPosition;
        }
        else {
            largest = position;
        }
        if(rightPosition <= array.length && array[rightPosition-1] > array[largest-1]){
            largest = rightPosition;
        }

        if(largest != position){
            swap(array,position-1,largest-1);
            maxHeapify(array, largest);
        }
    }

    public void maxHeapifyForSort(int[]  array, int position, int maxPos){

        int leftPosition = getLeft(position);
        int rightPosition = getRight(position);

        int largest = 0;

        if(leftPosition <= maxPos && array[leftPosition-1] > array[position-1]){
            largest = leftPosition;
        }
        else {
            largest = position;
        }
        if(rightPosition <= maxPos && array[rightPosition-1] > array[largest-1]){
            largest = rightPosition;
        }

        if(largest != position){
            swap(array,position-1,largest-1);
            maxHeapifyForSort(array, largest,maxPos);
        }
    }

    public void buildMaxHeap(int[] array){

        for(int i=(array.length)/2;i>0;i--){
            maxHeapify(array,i);
        }

    }

    public void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public void heapSort(int[] array){
        buildMaxHeap(array);
        for(int i=array.length;i>0;i--){
            swap(array,0,i-1);
            maxHeapifyForSort(array,1,i-1);
        }
    }

    public static void main(String args[]){

        int[] array = new int[]{4,1,3,2,16,9,10,14,8,7};
        System.out.println("Original Array : " + Arrays.toString(array));
        //new HeapSort().buildMaxHeap(array);
        new HeapSort().heapSort(array);
        System.out.println("After Sorting Array : " + Arrays.toString(array));


    }

}

Output : 

Original Array : [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
After Sorting Array : [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

 NOTE: I have shown two similar methods here maxHeapify(int[]  array, int position)
and maxHeapifyForSort(int[]  array, int position, int maxPos) but for sorting you will only need the second one. If your goal is to only create a max heap method one will do just fine. When we go for sort in each iteration we need to decouple indexes from the end so they are the maximum ones and hence we need a limit position to inform heapify function till where it should operate. What heapify does is that each element should have children which are smaller then itself.


NOTE :  Heap sort is an in place algorithm (in-place algorithm is an algorithm which transforms input using no auxiliary data structure).


Applications :  Heaps are generally used in priority queues ( min or max heap) so that you can retrieve the min or max element in O(1). Insertion will be log(N). It can be used to store realtime data. Lets say to keep score of top 3 people in a game given their scores are changing in realtime.

Related Links

• Heap sort Wiki