/*****************************************************************************/
/*                                                                           */
/*                          Heap Test Program                                */
/*                                                                           */
/*                    January 1998, Toshimi Minoura                          */
/*                                                                           */
/*****************************************************************************/

// Elements in the heap are stored in data[].

 
class Heap  {
  private int data[];           // storage for heap data
  private int last;             // index of last element in heap

  public Heap() {               // constructor
    data = new int[100];
    last = -1;                  // initially, heap is empty
  }

  public Heap(int initData[]) { // constructor
    data = new int[100];
    for (int i = 0; i < initData.length; i++) {
      data[i] = initData[i];
    }
    last = initData.length - 1; // initially, heap is empty
  }

  public void add(int x) {
    data[++last] = x;
    System.out.println("Item " + x + " added at location " + last);
    percolateUp(last);
  }

  public int removeMin() {
    if (last == -1) return -1;   // no item left
    int min = data[0];           // remove element at top of heap
    System.out.println("Item " + min + " removed from location 0");
    data[0] = data[last];        // move last element to emptified slot
    System.out.println("Item " + data[0] + " moved from location "
                        + last + " to location 0");
    if (last == 0) {
      last = -1;
      return min;
    };
    last--;                      // reduce heap size
    percolateDown(0);            // let moved element settle
    return min;
  }

  public void clear() {
    last = -1;
  }

  public void swap(int idx1, int idx2) {  // swap elements at idx1 and idx2
    int temp = data[idx1];
    data[idx1] = data[idx2];
    data[idx2] = temp;
    System.out.println("Item " + data[idx2] + " at location " + idx1 +
                  " and item " + data[idx1] + " at location " + idx2 +
                  " were exchanged");
  }

  public void percolateUp(int idx) {      // let element move up and settle
    System.out.println("percolate up item " + data[idx] + 
                       " at location " + idx);
    if (idx == 0) return;
    int parentIdx = (idx - 1) / 2;
    if (data[parentIdx] > data[idx]) { 
      swap(parentIdx, idx);               // move larger parent down
      percolateUp(parentIdx);
    }
  }

  public void percolateDown(int idx) {
    System.out.println("percolate down item " + data[idx] + 
                       " at location " + idx);
    int childIdx = idx * 2 + 1;
    if (childIdx > last) return;
    if (childIdx + 1 <= last && data[childIdx+1] < data[childIdx]) {
      childIdx = childIdx + 1;
    }
    if (data[idx] > data[childIdx]) {
      swap(idx, childIdx);
      percolateDown(childIdx);
    }
  }

  public void makeHeap() {           // convert an array into a heap
    for (int i = (last - 1) / 2; i >= 0; i--) {
      percolateDown(i);
    }
  }

  public void dataPrint() {                    // print stack content
     System.out.print("Heap: last = " + last + ", data = ");
      for (int i = 0; i <= last; i++) {
        System.out.print(data[i]);    // print every value in data[]
        if (i < last) System.out.print(", ");
      };
      System.out.println("");
  }
   
  static final int initData[] =  { 10, 3, 5, 6, 2, 7, 1 };  // initial data
  public static void main(String argv[]) {          
    System.out.println("main() started");
    Heap heap = new Heap(initData);
    heap.makeHeap();
    heap.dataPrint();                  // print heap content
    heap.add(8);
    heap.dataPrint();                  // print heap content

    int min = heap.removeMin();
    System.out.println("Removed item was " + min);
    heap.dataPrint();                  // print heap content
    heap.add(9);
    heap.dataPrint();                  // print heap content
    heap.add(4);
    heap.dataPrint();                  // print heap content

    min = heap.removeMin();
    System.out.println("Removed item was " + min);

    System.out.println("main() completed");
  }  
}