What is Heap sort?
It is a sorting algorithm which uses a binary heap data
structure.it compares the elements and organize it accordingly.
It has following steps.
- A heap is constructed. It kept the largest element as root element.
- A sorting procedure is followed. The root element is exchanged with the last item.
- The heap is reconstructed according to heap property.
- This process is repeated until all elements are arranged in ascending order.
Program:
import java.util.Arrays;
public class HeapSortEg {
public static void
heapSort(int[] a) {
int n =
a.length;
// let us
create max heap
for (int i = n
/ 2 - 1; i >= 0; i--) {
heapIt(a,
n, i);
}
// Extract the
elements one by one
for (int i = n
- 1; i > 0; i--) {
//
Exchange the root element with the last element
int temp =
a[0];
a[0] =
a[i];
a[i] =
temp;
// check
for Heap if it is reduced
heapIt(a,
i, 0);
}
}
private static void heapIt(int[] a, int n, int i) {
int large = i;
int a_left = 2
* i + 1;
int a_right =
2 * i + 2;
// If the left
child is greater than root
if (a_left
< n && a[a_left] > a[large]) {
large =
a_left;
}
// If the
right child is greater than largest so far
if (a_right
< n && a[a_right] > a[large]) {
large =
a_right;
}
// Check the
largest number is not root
if (large !=
i) {
int swap =
a[i];
a[i] =
a[large];
a[large] =
swap;
//
Recursively heapIt the affected sub-tree
heapIt(a,
n, large);
}
}
public static void
main(String[] args) {
int[] a = {22,
10, 31, 15, 61, 87, 3, 16};
System.out.println("Original array is: " +
Arrays.toString(a));
heapSort(a);
System.out.println("The Sorted array: " + Arrays.toString(a));
}
}
Output:
C:\raji\blog>javac HeapSortEg.java
C:\raji\blog>java HeapSortEg
Original array is: [22, 10, 31, 15, 61, 87, 3, 16]
The Sorted array: [3, 10, 15, 16, 22, 31, 61, 87]
This is the simple way to create the Heap sort in java. Hope,
this code is useful to you. Keep Coding!!!
No comments:
Post a Comment