Heap Sort in Java is used to sort integer values of an array. Like quicksort, insertion sort, bubble sort and other sorting methods, heap sort is used to sort an unsorted list.
Heap Sort in Java is used to sort integer values of an array. Like quicksort, insertion sort, bubble sort and other sorting methods, heap sort is used to sort an unsorted list. When compared to other sorting methods heap sort is the slowest but is more efficient and reliable in large data sets. In heap sort, an array can be divided in two parts: a heap (which has the unsorted list) and a sorted array.
Heap is of two types:
- Max heap: Max heap is a binary tree that has roots greater than its child roots.
- Min heap: Min heap has minimum roots than its child roots.
Min heap and Max heap decide the direction of sorted array.
In heap sorting algorithm the heap build is used to rebuild the heap.
The complexity of the heap sort is O(n.log n).
In the following example, Build Heap algorithm is used that removes the biggest element from a heap and place it in the second array. These steps are followed till all elements in heap are replaced into array.
Steps in heap sort:
- The Root node is replaced by the rightmost leaf.
- Store the root node in an array.
- Re-check the heap for the biggest element
- Repeat steps 1 and 3 until values in heap is not 0.
Example of Heap Sort in Java:
public class eap_Sort{
public static void main(String a[]){
int i;
int arr[] = {1,3,4,5,2};
System.out.println("\n Heap Sort\n---------------\n");
System.out.println("\n Unsorted Array\n\n");
for (i = 0; i < arr.length; i++)
System.out.print(" "+arr[i]);
for(i=arr.length; i>1; i--){
fnSortHeap(arr, i - 1);
}
System.out.println("\n Sorted array\n---------------\n");
for (i = 0; i < arr.length; i++)
System.out.print(" "+arr[i]);
}
public static void fnSortHeap(int array[], int arr_ubound){
int i, o;
int lChild, rChild, mChild, root, temp;
root = (arr_ubound-1)/2;
for(o = root; o >= 0; o--){
for(i=root;i>=0;i--){
lChild = (2*i)+1;
rChild = (2*i)+2;
if((lChild <= arr_ubound) && (rChild <= arr_ubound)){
if(array[rChild] >= array[lChild])
mChild = rChild;
else
mChild = lChild;
}
else{
if(rChild > arr_ubound)
mChild = lChild;
else
mChild = rChild;
}
if(array[i] < array[mChild]){
temp = array[i];
array[i] = array[mChild];
array[mChild] = temp;
}
}
}
temp = array[0];
array[0] = array[arr_ubound];
array[arr_ubound] = temp;
return;
}
}}
Output:
C:\array\sorting>Javac heap_Sort.java
C:\array\sorting>java heap_Sort
Heap Sort
---------------
Unsorted Array
1 3 4 5 2
Sorted array
---------------
1 2 3 4 5