Computer Science 15-110, Fall 2009
Class Notes:  JCF Part 2:  Collections class, PriorityQueues (and Heapsort)

In class today, we explored the Collections class:
   http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html

We also explored the PriorityQueue class:
   http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html

We then used a PriorityQueue to write a 4-line version of heapsort.  To sort an array:

• Create a PriorityQueue
• Add every element in the array to the PriorityQueue
• Remove each smallest (or largest) remaining element in turn and store it back into the array.

We timed this version of heapsort, and while it was a bit slower than mergesort or quicksort, it was clearly O(NlogN), and so it was very fast, and gosh it only required 4 lines of code to write!

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem