// TestHeapSort.java ปรับปรุง : 2548-06-08 ()
// เคล็ด : ใช้หลักการของ Heap sort 
// โปรแกรมสำหรับ จัดเรียงข้อมูล แบบ Heap
// แหล่งอ้างอิง 
//   http://www.thaiall.com/class
//   http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/heapsort.html
//   http://www2.hawaii.edu/~copley/665/HSApplet.html
//   http://www-cse.uta.edu/~holder/courses/cse2320/lectures/applets/sort1/heapsort.html
//   http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm
//   http://www.java2s.com/ExampleCode/Collections-Data-Structure/Heapsort.htm
//   http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
//   http://www.cp.eng.chula.ac.th/%7Eu45dtn/mergesort/mergesort.htm (มีแต่ source กับ awt)
//   http://www.java2s.com/ExampleCode/Collections-Data-Structure/Sort-Search.htm
//
import java.io.IOException;
class MyNode {
  private int iData; 
  public MyNode(int key) {
    iData = key;
  }
  public int getKey() {
    return iData;
  }
}
public class TestHeapSort {
  private MyNode[] heapArray;
  private int maxSize;
  private int currentSize; 
  public TestHeapSort(int mx) {
    maxSize = mx;
    currentSize = 0;
    heapArray = new MyNode[maxSize];
  }
  public MyNode remove() { 
    MyNode root = heapArray[0];
    heapArray[0] = heapArray[--currentSize];
    trickleDown(0);
    return root;
  }
  public void trickleDown(int index) {
    int largerChild;
    MyNode top = heapArray[index]; 
    while (index < currentSize / 2) {
      int leftChild = 2 * index + 1;
      int rightChild = leftChild + 1;
      if (rightChild < currentSize && heapArray[leftChild].getKey() < heapArray[rightChild].getKey())
        largerChild = rightChild;
      else
        largerChild = leftChild;
      if (top.getKey() >= heapArray[largerChild].getKey())  break;
      heapArray[index] = heapArray[largerChild];
      index = largerChild; 
    }
    heapArray[index] = top;
  }
  public void displayHeap() {
    int nBlanks = 32;
    int itemsPerRow = 1;
    int column = 0;
    int currentIndex = 0; 
    while (currentSize > 0) {
      if (column == 0) for (int k = 0; k < nBlanks; k++) System.out.print(' ');
      System.out.print(heapArray[currentIndex].getKey());
      if (++currentIndex == currentSize) break;
      if (++column == itemsPerRow) {
        nBlanks /= 2; 
        itemsPerRow *= 2; 
        column = 0; 
        System.out.println(); 
      } else
        for (int k = 0; k < nBlanks * 2 - 2; k++) System.out.print(' '); 
    } 
  }
  public void displayArray() {
    for (int j = 0; j < maxSize; j++)
      System.out.print(heapArray[j].getKey() + " ");
    System.out.println("");
  }
  public void insertAt(int index, MyNode newNode) {
    heapArray[index] = newNode;
  }
  public void incrementSize() {
    currentSize++;
  }
  public static void main(String[] args) throws IOException {
    int size, i, d[] = {51,46,14,35,22};
    size = 5;
    TestHeapSort theHeap = new TestHeapSort(size);
    for (i = 0; i < size; i++) {
      MyNode newNode = new MyNode(d[i]);
      theHeap.insertAt(i, newNode);
      theHeap.incrementSize();
    }
    System.out.print("Before :");
    theHeap.displayArray();
    for (i = size / 2 - 1; i >= 0; i--)
      theHeap.trickleDown(i);
    theHeap.displayHeap();
    for (i = size - 1; i >= 0; i--) {
      MyNode biggestNode = theHeap.remove();
      theHeap.insertAt(i, biggestNode);
    }
    System.out.println();
	System.out.print("After  :");
    theHeap.displayArray();
  }
}