/******************************************************************************
Online Java Compiler.
Code, Compile, Run and Debug java program online.
Write your code in this editor and press "Run" button to execute it.
*******************************************************************************/
public class Main
{
public static void main (String[] args) throws Exception
{
Integer[] arr = {3, 2, 1, 4};
HeapClass<Integer> h = new HeapClass<Integer>();
System.out.println("array: " + h.getClass().getDeclaredField("array"));
h.heapSort(arr);
for (int i = 0; i < arr.length; i++)
System.out.println(arr[i]);
}
public static class HeapClass <E extends Comparable <E>>
{
private int lastposition;
private E[] array;
public void heapSort(E[] arr)
{
lastposition = arr.length - 1;
array = (E[]) new Comparable[arr.length * 2];
for (int i = 0; i < arr.length; i++)
add(arr[i]);
for (int i = 0; i < arr.length; i++)
array[arr.length - i - 1] = remove();
arr = array;
}
public void add (E obj)
{
lastposition++;
array[lastposition] = obj;
trickleUp(lastposition);
}
public void swap (int from, int to)
{
E temp = array[from];
array[from] = array[to];
array[to] = temp;
}
public void trickleUp(int position)
{
if (position == 0)
return;
int parent = (int) Math.floor((position - 1) / 2);
if (((Comparable <E>) array[position]).compareTo(array[parent]) > 0)
{
swap(position, parent);
trickleUp(parent);
}
}
public E remove()
{
E temp = array[0];
swap(0, lastposition--);
trickleDown(0);
return temp;
}
public void trickleDown(int parent)
{
int left = 2 * parent + 1;
int right = 2 * parent + 2;
if (left == lastposition && ((Comparable <E>) array[parent]).compareTo(array[left]) < 0)
{
swap(parent, left);
return;
}
if (left == lastposition)
return;
if (right == lastposition)
{
E max;
int pos;
if (((Comparable <E>) array[left]).compareTo(array[right]) < 0)
{
max = array[right];
pos = 1;
}
else
{
max = array[left];
pos = 0;
}
if(((Comparable <E>) array[parent]).compareTo(max) < 0)
{
if (pos == 0)
{
swap(parent, left);
return;
}
else
{
swap(parent, right);
return;
}
}
return;
}
if (left >= lastposition || right >= lastposition)
return;
if (((Comparable <E>) array[left]).compareTo(array[right]) > 0 && ((Comparable <E>) array[parent]).compareTo(array[left]) < 0)
{
swap(parent, left);
trickleDown(left);
}
if (((Comparable <E>) array[parent]).compareTo(array[right]) < 0)
{
swap(parent, right);
trickleDown(right);
}
}
}
}
