CSC 17 Lab: Flexible Priority Heap
 
In this lab you will improve on the BinaryHeap class I wrote by defining
a subclass with new methods and by overriding some of my methods.
Alternatively, you can write your class from scratch (instead of writing
a subclass of my class).  But you must still implement the same interface
and implement the same underlying algorithm of a Binary Heap.

You should know that Java has a built-in class:
java.util.PriorityQueue that implements a Heap.  In general, try avoid
using 'import java.util.*' to avoid name clashes: import only what you
need.  In fact, our PriorityQueue interface was designed to be consistent
with the methods you can call on that structure.  However, this data
structure may not give us everything we need from a priority queue,
namely what to do when the priority of an object CHANGES.  When this
occurs, the position of the object in the heap tree likely becomes
invalid and must be adjusted.  Right now, with both my BinaryHeap and
with java.util.PriorityQueue, the only way to do it is to find and
remove the object first, then re-insert it.  This takes O(n) time.
But it should be do-able in O(log n) time provided we are *aware* of
where in the heap the object is.  That is, these objects must also
store the index of where in the heap it currently resides.  This will
allow us to avoid the O(n) cost of finding an object's position in the
heap before swapping it upwards or downloards.

We will require that objects to be stored in a 'FlexPriorityQueue' implement
the following interface:

public interface HeapValue<T> extends Comparable<T>
{
    int getIndex(); // get the index of this object in the heap
    void setIndex(int x); // set the index of this object in the heap
    // int compareTo(T x); // inherited from Comparable
}
// note we can optionally maintain a pointer to the heap that contains this object
// and require functions getHeap and setHeap, but I've decided to leave this out.
// Thus it must be clear from context what is the heap that these object belongs to.

Here's a sample class that implements HeapValue (which means it must
also implement compareTo).  

class scholar implements HeapValue<scholar>
{
    public final String name;
    protected double gpa; // with up to 3 digits of precision
    public scholar(String n, double g) // constructor
	{
	    if (n==null || g<0 || g>4.0) throw new RuntimeException("invalid");
	    name=n;  gpa=g;
	}
    public int compareTo(scholar other)
    {
	return (int)(gpa*100+0.5) - (int) (other.gpa*100+0.5);
    }

    public void updateGPA(double g)  // But the "priority" can change!
    {
	if (g>0 && g<=4.0) gpa = g;
    }

    protected int hi = -1; // heap index, -1 means index invalid
    public int getIndex() { return hi; }
    public void setIndex(int n) { hi=n; }
  
}//student scholar  class

'scholar' objects are prioritized by their gpa values, which may change
over time. Each time updateGPA is called, the position of the scholar
in the priority queue must also be updated. 

Each time you place a HeapValue object inside the heap array
(H[i]=object) you must call H[i].setIndex(i) to record the index
inside the object itself.  The setIndex function, although required to
be public, should only be called whenever the object is being queued
or swapped (inside your FlexQueue class).  Changing the index
externally may destroy the properties of the heap and render it
useless.  However, your heap functions should first check if the index
where the object is stored in the array is the same as returned by
getIndex.  That is, if H[i]==x, then x.getIndex() == i, or:

     H[x.getIndex()] == x  (and yes, you want ==, not just .equals)

Equivalently:
     H[i].getIndex() == i  if i>==0 && i<size

If this condition is not met, you should throw a new
RuntimeException("Somebody messed with my heap indices!");   
Thus, although setIndex is a public function, your program will provide
runtime error checks against its corrupted use.

Note that when you insert/delete or reposition a HeapValue object,
it's not just the heap index of that object that must be set, but all
objects that it may get swapped with.

======================================================================
******  Your main objective is to implement a new operation: *********
======================================================================

Inside the PriorityQueue interface there's a function specification
that has a dummy default:

default boolean reposition(T x) { return false; }

The only purpose of the default implementation is to make the implemenation
of this feature optional.  My BinaryHeap class does not implement it, so
it inherits the default and always returns false after doing absolutely
nothing.  You are to provide the real implementation.

To get you started, your subclass can begin this way 

public class FlexBinaryHeap<T extends HeapValue<T>> 
             extends BinaryHeap<T> implements PriorityQueue<T>
{
    public FlexBinaryHeap(int cap, boolean maxmin) { super(cap,maxmin); }
    public FlexBinaryHeap() { super(); }

    @Override
    @SuppressWarnings("unchecked") /* don't use unless you're REALY sure...*/
    protected T[] makearray(int n) { return (T[]) new HeapValue[n]; }

    //...
    // implement a real  public boolean reposition(T x) {...}
}

****** Remember, at no time may you edit my superclass: you may only override.
With few exceptions, this will be a general requirement in all assignments:
write all your code separately, never edit my code.  However, you also need
to *reuse* my code whenever possible.  For this assignment, you may only
edit the "scholar" class if you wish to make it more interesting.

===============================
You can devise your own tests, but here's a main that you can use to 
test your program (change name of your flexqueue class if necessary):

public static void main(String[] av)
    {
        scholar a = new scholar("A",1.5);
        scholar b = new scholar("B",2.5);
        scholar c = new scholar("C", 3.3);
        scholar d = new scholar("D",3.0);
        scholar e = new scholar("E",3.2);
        scholar[] Scholars = {a,b,c,d,e};
        FlexBinaryHeap<scholar> FPQ = new FlexBinaryHeap<scholar>();
        for (scholar x:Scholars) FPQ.add(x);
        System.out.println("top scholar: "+FPQ.peek().name);
        // priorities change over time...
        d.updateGPA(3.5);  FPQ.reposition(d);
        e.updateGPA(3.7);  FPQ.reposition(e);
        System.out.println("after GPA updates...");
        while (FPQ.size()>0) System.out.println(FPQ.poll().name);
    }

===============================
Using the HeapDisplay program.
For small-enough heaps, you can see the result of your program by displaying
the heap graphically.  See the main in my BinaryHeap.java program and the
(commented-out) main in HeapDisplay.java to see how it's done.  This program
can in fact display any initial portion of an array in the shape of a 
complete binary tree: it's called on the underlying array and the size, which
indicates how many initial values are to be considered to be in the tree.
===============================
Part II.

Implement the "heapify" (or Floyd's "Building a Heap") procedure.
This procedure should rearrange any array to have the characteristics
of a Heap by starting at the "end" of the heap, and call swapdown on
each element.  However, to be more efficient, you should take
advantage of the fact that in any complete binary tree, exactly
(size+1)/2 of the elements are leaf nodes, which don't have to be
touched.  The total time complexity of this operation is surprisingly
O(n), not just O(n*log n) as you might expect (read Wikipedia
analysis).

First: do a little bit of math: if there are (size+1)/2 leaf nodes,
then how many non-leaf nodes are there, and what is the index of the
last non-leaf node?  Then you can write heapify relatively easily with
a loop:

start at the index of the last non-leaf node, counting backwards until index
0, and call swapdown on each index:

protected void heapify()
{
  i = index of last non-leaf node
  while (i>=0) swapdown(i--); 
}

Add the following constructor to your class, which accepts any array,
along with a size argument that indicates the initial part of the array
that should be considered, and calls heapify on it:

    public FlexBinaryHeap(T[] A, int s)
    {   if (A==null || A.length<1 || s<0 || s>=A.length)
	    throw new RuntimeException("invalid heap array");
	H = A;  size = s;
	heapify();
    }

Write code in main to demonstrate heapify.

===============================
Part III.

For this part of the lab, you need to invent a new sorting
algorithm for an array that runs in worst-case O(n*log(n)) time using
a heap (BinHeap is enough).  Hint: if you call n dequeue() operations,
you will get n values in decreasing order, and the time will be
n*log(n) since each dequeue() takes log(n) time.  Make sure that your
algorithm is polymorphic using the CompareTo interface (look at
implementaion of QuickSort,MergeSort for hints.)

CHALLENGE:  Write the "heapsort" algorithm using O(1) extra memory:
in other words, try to use the array itself as the heap array.  This will
give you a sorting algorithm that, at least theoretically, have the
advantage of mergesort, which is worst-case n*log(n), as well as quicksort,
which doesn't require significant extra memory.