Heapsort is a comparison-based sorting algorithm. It can be thought of as an improved selection sort: like that algorithm, it divides its 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.
The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.
Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n*logn) runtime.
Heapsort is an in-place algorithm, but it is not a stable sort.
public class HeapSort {
/**
* Heap sort logic.
* @param array
*/
private static void heapSort(int[] array) {
int size = array.length;
/** Heapify the complete array. */
for (int i=size/2-1; i>=0; i--) {
heapify(array, i, size);
}
/**
* 1. Swap the root element with last unsorted element.
* 2. Heapify the array excluding the sorted sub-array.
* 3. Repeat the step#1 and step#2.
* */
for (int i =size-1; i>=0; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
heapify(array, 0, i);
}
}
/**
* To heapify a subtree rooted with node i which is an index in arr[]. n is size of heap
* @param array
* @param i
* @param n
*/
private static void heapify(int[] array, int i, int n) {
int left = 2*i+1;
int right = 2*i+2;
int largest = i;
/** Choose biggest element between left and right child. */
if(left<n && array[largest]<array[left] ) {
largest = left;
}
if(right<n && array[largest]<array[right]) {
largest = right;
}
/**
* 1. Swap the largest element to root.
* 2. Heapify recursively.
**/
if (largest != i) {
swap(array,largest, i);
heapify(array, largest, n);
}
}
public static void main(String args[]) {
int[] array = {22, 19, 23, 15, 16, 17};
heapSort(array);
System.out.print("Sorted array is: ");
printArray(array);
}
private static void printArray(int array[]) {
int n = array.length;
for (int i=0; i<n; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
