CSE 373: Data Structures and Algorithms, Winter 2013

Homework 5 (The Even-More-Amazing Heap) FAQ

Q: What are some good resources or examples I can look at to get started on this program?

A: Look at the HeapPriorityQueue example from Friday's lecture. If you want to read more about implementing a priority queue using an heap, you can read this sample Building Java Programs Chapter 18 on heaps (please do not distribute!). The Weiss textbook also has a lot of good coverage of heaps in its Chapter 6.

Q: In Part A, why doesn't the compiler allow my Comparator to be passed when constructing a PriorityQueue?

A: Confusingly, the PriorityQueue constructor that accepts a Comparator also requires you to pass the initial capacity (heap array size) for the queue to use. You can pass any capacity you want; maybe use a big number like 100 or 1000 so the queue doesn't need to resize much.

PriorityQueue<Point> pqueue = new PriorityQueue<Point>(1000, new MyComparator(...));

If you are already using the constructor properly but still see this error, you may have written your comparator class improperly. Make sure that it implements Comparator<Point> and has a proper compare method with the right header.

Q: What does this error mean? Exception in thread "main" java.lang.ArrayStoreException: java.awt.Point

A: It probably means that you declared your array as being Comparable, but you should just declare it as an array of Objects because Point objects are not comparable.

Q: What does this error mean? type argument Point is not within bounds of type-variable E

A: It probably means that you declared your HeapPriorityQueue's type parameter E as being extends Comparable<E>, but you should not declare it with any extends clause because it needs to allow types that are not comparable (using a Comparator to order them instead).

Q: If my heap array is not declared to be of type Comparable, then how do I call compareTo on it?

A: Try something like this:

int comp = ((Comparable<E>) elements[index1]).compareTo(elements[index2]);

Q: On Part B, I get a compiler warning or a casting exception when I try to cast my array of E objects. Is that okay? What should I do?

A: That's just a Java thing; look at Friday's HeapPriorityQueue for an example that casts properly. You can also add @SuppressWarnings("unchecked") above your method/constructor header to remove the error. This is okay and acceptable style in this one particular case. (Please don't use @SuppressWarnings elsewhere, only in this particular situation.) Your line of code to construct your array should look something like this:

elements = (E[]) new Object[10];

Q: Am I required to use a StringBuilder in my toString method?

A: No. It's much faster than just concatenating a String, but we don't require it.