HeapSort2

import java.util.*;

/**
 * This class implements the PriorityQueue2 interface using
 * a binary heap.
 *
 * the basic idea is that the node whose index is k
 * has children stored with indexes 2*k and 2*k+1 for left/right
 * children, respectively. The root of the binary heap has index 1.
 *
 * @author Your Name
 */

public class HeapSort2 implements PriorityQueue2
{
  private List items;
  private int mySize;   // since index 0 is unused, mySize is items.size() - 1

  /**
   * Constructs an empty priority queue.
   */
  public HeapSort2()
  {
    items = new ArrayList();
    items.add(null);            // first add should go at index 1 since
                                // index 0 is unused
    mySize = 0;
  }

  public void add(Object obj)
  {
    // PSEUDOCODE:
    // Add 'obj' to end of 'items' list
    // Increment mySize
    // Now 'heap up' the obj added to end of list:
    //   init index k to current index of 'obj'
    //   while (not done && k is not pointing to root, ie k > index 1)
    //   {
    //      if (value at parent node is greater than 'obj')
    //      {
    //          copy value at parent node to k node
    //          move k to parent node
    //      }
    //      else
    //          done -> stop loop
    //   }
    //   set 'heaped up' obj to its final position at latest value of k
  }

  public Object removeMin()
  {
    // PSEUDOCODE:
    // if (heap isn't empty)
    // {
    //    fetch min value to be returned
    //    replace min value on the heap with the last element in 'items' list
    //    decrement mySize by 1
    //    if (mySize > 1)
    //       call 'heapify' from root down, where root is at index 1
    //    return min value
    // }
    // return null
    return null;
  }

  public Object peekMin()
  {
    // PSEUDOCODE:
    // return value at index 1 of 'items' list
    return null;
  }

  public boolean isEmpty()
  {
    // PSEUDOCODE:
    // return true if mySize is zero
    return true;
  }

  /**
   * preconditon: subheaps of hroot satisfy heap property (and shape)
   * postcondition: heap rooted at hroot satisfies heap property
   */
  private void heapify(int hroot)
  {
    // SEE BELOW FOR EXAMPLE
    //
    // PSEUDOCODE:
    // 'last' = element to "heap down" i.e. element at index 'hroot'
    // init index k to hroot
    // while (2*k <= mySize)   // index k has at least one child
    // {
    //    // find minimal child, start with left, then check right
    //    child = 2*k   // left child
    //    if (child < mySize)   // k has 2 children
    //        if (right child < left child)
    //           child++    // go to right child instead because it's smaller
    //    // if item to be added <= child, stop and add the item
    //    if (last <= element at 'child')
    //        break         // 'last' is smaller than either child, so leave it alone
    //    else  // 'last' is larger than one or both children
    //    {
    //        copy smallest child to node k
    //        k = child     // now k points to child's index
    //    }
    // }
    // // at this point, element at 'k' has no children OR
    // // is smaller than any of its children -> put 'last' in its final spot at k
    // put 'last' at node k
  }
}

/*******************************************************************************
 * HEAPIFY EXAMPLE:
 *
 * Original array in which '13' is being removed as 'min' value and remaining list
 * will be 'heaped down'
 *
 * index:   0   1   2   3   4   5   6   7   8   9   10  11  12  13
 * value:   -   13  18  24  22  38  56  30  34  97  95  83  81  87
 *
 * What specific elements in the array are replaced with:
 *
 * index:   0   1   2   3   4   5   6   7   8   9   10  11  12  13
 *
 * (last leaf)  87
 * heapify      18
 *                  22
 *                          34
 *                                          87
 *
 * Tracing Table:
 *
 * k    child   items(child)    items(child+1)
 *---   -----   ------------    --------------
 * 1    2           18              24
 * 2    4           22              38
 * 4    8           34              97
 * 8    (none) <-- put 'last' here
 *
 *****************************************************************************/