// Java program that uses max heap to do the sorting
public class HeapSortExample
{
public static void maxHeapSort(int a[])
{
int size = a.length;
// rearranging array elements so that it
// resembles max heap
for (int j = size / 2 - 1; j >= 0; j--)
heapify(a, size, j);
// One by one extract the top element, which is
// also the maximum element from the heap
for (int j = size - 1; j >= 0; j--)
{
// Moving the maximum element of the current heap to the end
int tmp = a[0];
a[0] = a[j];
a[j] = tmp;
// invoking method heapify on the reduced heap
heapify(a, j, 0);
}
}
// The heapfiy() method does the rearrangement of elements of
// the given input array to resemble it like a max heap
// Element present at the index j resembles the root of the max heap
// length gives the size of the max heap
static void heapify(int a[], int length, int j)
{
int highest = j; // assign highest as root
int left = 2 * j + 1; // leftChild = 2 * j + 1
int right = 2 * j + 2; // rightChild = 2 * j + 2
// If the root element is smaller the left child
if (left < length && a[left] > a[highest])
highest = left;
// If the root element so fat is smaller the right child
if (right < length && a[right] > a[highest])
highest = right;
// If root is not the highest
if (highest != j)
{
int change = a[j];
a[j] =