CSC 17 Priority Heap Lab

This lab will serve several purposes:

     a. understand and use the heap data structure
     b. understand the time complexity of heap algorithms.
     c. use inheritance to improve a Heap implementation.

Download my Heap.java and heapdisplay.java programs.
All your code for this lab should be in a separate file myheap.java
with a class.  Compile your program together with the two you downloaded:
javac myheap.java Heap.java heapdisplay.java

To use the heapdisplay program, you can add the following method to your
subclass of Heap (never edit the Heap superclass itself - you'll "void the
warrantee"):

  public void drawheap() // use only with heapdisplay.java program
  {
      heapdisplay W = new heapdisplay(1024,768);
      W.drawtree(H,size);
  }

Call drawheap will pop up a window and draw the heap graphically.


YOU ARE NOT ALLOWED TO EDIT Heap.java, all changes you wish to make must
be made in the subclass.

public class myheap<T extends Comparable<T>> extends Heap<T>
{ 
    // constructors of the subclass should be written this way:
    public myheap(int max) { super(max); }
    public myheap(T[] A, int size) {super(A, size);}  
    public void drawheap() // use only with heapdisplay.java program
    { 
      heapdisplay W = new heapdisplay(1024,768);
      W.drawtree(H,size);
    }
    // ... other methods (see below)

    // create a main to test
}

Part 1:

We can use the basic characteristics of a heap to implement a sorting
    algorithm as follows:

 1. Given an array A of comparable objects, insert the elements into
    a heap.

 2. Now, reconstruct the A array (backwards) by deleting the maximum (top) 
    element from the heap one by one.  That is write a loop that starts
    at the last index of the array: for(int i=A.length-1;i>=0;i--)...

 This algorithm runs in (worst-case) O(n*log n) time since you need to
 perform n insert operations and each insert takes log(n) time.  You
 then perform n deleteMax operations, each also taking log(n) time,
 which givens you 2*n*log(n) steps.  Implement this sorting algorithm.
 You can implement this algorithm as an independent polymorphic
 function:

 public static <S extends Comparable<S>> void heapsort(S[] A) // sorts array A
 // this funciton is independently polymorphic (parameterized by <S>)
{ // outline:
  // 1.create a Heap<S> HA with capacity same as A.length
  // 2.insert every value in A into HA
  // 3.use a backwards loop to fill array with HA.deleteTop() values
}

Test your algorithm with random data:
     
        int n = 100000; // sort 100K numbers
	Integer[] A = new Integer[n];
	for(int i=0;i<A.length;i++)
	    A[i] = (int)(Math.random()*100*n);
	heapsort(A); // assume called from within main in myheap
	for(int i=0;i<A.length-1;i++)
	    if (A[i]>A[i+1]) System.out.println("OOPS"); // shouldn't print this

Part 2:

    Study and understand the insert and deleteTop functions 
    written in class (and on homepage), then study the "Building a Heap"
    algorithm described in the handout (on slide 11).  Implement the
    build-heap algorithm as described, but DO NOT USE RECURSION.

    Notice that in the Heap class (therefore inherited by your class) one
    of the constructors take an array as an argument and sets the internal
    H to point to it.  The array you pass in is generally not in the form
    of a heap.  So we should write a procedure to make it into a heap.

    Add a new method to your heap subclass:  

    	public void makeheap()
    
    That transforms the H array into a heap using the build-heap and
    swapdown algorithms.  Optionally, you can change your second
    constructor to always call makeheap.

    Use my heapdisplay program to check that your program is actually
    creating a heap.

additional hint: call the swapdown function in the superclass

Part 2b: 

The sorting algorithm of part 1 uses twice as much memory because the
array representing the heap is different from the array to be sorted.
You need to write a new version of heapsort (heapsort2) that correct
this problem.  You can pass the array to be sorted into a heap and
call makeheap().  But a heap is not the same as a sorted array. You
still need to call deleteTop (deleteMax) in a loop.  How can you
rearrange the array so that it is sorted, without using an additional
array?  One simple solution is, instead of deleting the largest value
at the top, SWAP the top value with the value at the end of the heap.
You should write a program that does this, call deleteTop and insert
the value back at the end of the heap (be aware that the size variable
is changed by deleteTop).
 
This time, add the following non-static function to your myheap class

public void heapsort() { ... }

This means that to sort an array of Integer values from main, you need to:

// given Integer[] A, 
myheap<Integer> HA = new myheap<Integer>(A,A.length);
HA.makeheap(); // if not already called from constructor
HA.heapsort();
// at this point, A should be sorted and HA should be "empty" because
// HA.size() will be 0, even though the values in the array stay put.

Generate tests as in part 1.

///
Part 3:

  Unlike insert and delete, searching for an element in a heap is
still worst-case O(n) and not O(log n).  There's a simple search
algorithm in the superclass.  This algorithm just searches the
underlining array H for x.  It does not take any advantage of the
structure of the heap.  For example, if the top element of the heap is
5 and we're searching for 6, we can immediately conclude that it's not
in the tree.  In general, if x is larger than the number at a certain
node in the tree, then we know that it cannot be in the "subtree"
beneath that node.  You need to implement a better search algorithm
that takes advantage of this fact.  The algorithm will still be worst
case O(n) but will be faster than the naive algorithm above.

Your new search function will override the superclass version.

A few hints about this problem:

1.  Don't think of the structure as an array but as a tree.
2.  Think recursively: what does it MEAN for a number to be in a heap:
    it can be equal to the root, or if it's less than the root, it 
    could in the left subtree or in the right subtree.
    The base case of the induction is either when you've found what you're
    looking for, or when you can conclude that the value can't possibly be
    in the tree.
   
3.  Your new function may take an additional parameter, such as the
    current index of the node that you're searching (start with 0 the root).
4.  I can write this program using a single return statement:

    return ... && ... && (... || ... || ...);

    You can take 3 or 4 lines but anything much longer would be wrong.