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?