import java.util.*;
/* Define a Max-Heap
* @author Lin Chen
* @since 10.02.2017
*/
public class Heap
{
/* Get the example in CLRS
* @return an intger array
*/
public static int [] getArray()
{
int array [] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
return array;
}
/* Get an random array
* @return an random integer array
*/
public static int [] randArray(int size)
{
int array [] = new int[size];
Random r = new Random();
for(int i = 0; i < size; i++)
array[i] = r.nextInt(100);
return array;
}
/* Get the left child
* @param i index of current node
* @return index of left child
*/
public static int getLeft(int i)
{
return i*2+1;
}
/* Get the right child
* @param i index of current node
* @return index of right child
*/
public static int getRight(int i)
{
return i*2+2;
}
/* Maintin the max-heap property of a subtree rooted at index i
* @param array an integer array
* @param i index of current node
* @param n index of last node of the subtree
*/
// O(lgn)
public static void maxHeapify(int [] array, int i, int n)
{
int l = getLeft(i);//get left child
int r = getRight(i);//get right child
int largest = i;
if(l <= n && array[l] > array[i])
largest = l;
if(r <= n && array[r] > array[largest])
largest = r;
if(largest != i)
{
int temp = array[i];
array[i] = array[largest];
array[largest] = temp;
maxHeapify(array, largest, n);
}
}
/* Create the heap tree for input array
* @param array an integer array
*/
// O(nlgn)
public static void buildMaxHeap(int [] array)
{
for(int i = (array.length/2-1); i >= 0; i--)
{
maxHeapify(array, i, array.length-1);
}
}
/* Sort an array with heap tree
* @param array an integer array
*/
// O(nlgn)
public static void heapSort(int [] array)
{
buildMaxHeap(array);
display(array);
for(int i = array.length-1; i > 0; i--)
{
int temp = array[0];
array[0] = array[i];
array[i] = temp;
maxHeapify(array, 0, i-1);
}
}
/* Display an integer array
* @param array an integer array
*/
public static void display(int [] array)
{
for(int i = 0; i < array.length; i++)
System.out.printf("%5d", array[i]);
System.out.println();
}
/* Test heap tree
*/
public static void main(String args[])
{
int [] array;
//array = getArray();
array = randArray(10);
display(array);
heapSort(array);
display(array);
}
}
