cs230 Lecture Notes
Spring 2002
Week 12, Monday

Solutions to Homework 9 are on the web (and are today's handout).

Homework 10 is due today.  Homework 11 is due next Monday.

Before lab tomorrow!!!
Read Homework 11 and the handout on Huffman codes!!!


Today's topics
--------------

1) Heap implementation of a PriorityQueue

2) Heap performance analysis


The Heap contains a Vector as an instance variable

public class Heap {
    Vector v;

    public Heap () {
	v = new Vector ();
	v.add ("narf");
    }

    public boolean empty () {
	return v.size() == 1;
    }
}

We initialize the Vector with a dummy value that fills the
zero-eth location.

To put something into the heap, we add it to the end and
let it trickle up:

    public void insert (Comparable c) {
	v.add (c);

	int i = v.size()-1;
	while (i>1) {
	    int parent = i/2;
	    if (compare (i, parent) > 0) {
		swap (i, parent);
	    } else {
		break;
	    }
	    i = parent;
	}
    }

When i==1, we are at the root.

To remove, we swap the root with the last element, and
remove the last element:

    public Object remove () {
	int i = v.size()-1;
	swap (1, i);
	Object result = v.remove (i);
	reheapify (1);
	return result;
    }

But now the thing at the top of the heap isn't necessarily
the biggest, so we have to reheapify, which is best done
recursively:

    private void reheapify (int i) {
	int left = 2*i;
	int right = 2*i + 1;
	boolean winleft = compare (i, left) >= 0;
	boolean winright = compare (i, right) >= 0;

	if (winleft && winright) return;
	if (compare (left, right) > 0) {
	    swap (i, left);
	    reheapify (left);
	} else {
	    swap (i, right);
	    reheapify (right);
	}
    }

The compare method is very safe: it works even if an element
is non-existent or null.

    private int compare (int i, int j) {
	Comparable c1 = (Comparable) get (i);
	Comparable c2 = (Comparable) get (j);

	if (c1 == null) {
	    if (c2 == null) {
		return 0;
	    } else {
		return -1;
	    }
	}
	if (c2 == null) return 1;
	return c1.compareTo (c2);
    }

    private Object get (int i) {
	if (i >= v.size()) {
	    return null;
	} else {
	    return v.get(i);
	}
    }



Performance analysis
--------------------

How long does insert take as a function of the number of
nodes in the tree?




How long does remove take as a function of the number of
nodes in the tree?