Announcement: until further notice, my office hours are 1-3pm Mondays
and Wednesdays, and by appointment.

Sorry, the programming part of hw1 is not ready yet, I'll work on it
over the weekend, and release it by Monday.  Meanwhile, the written
part of hw1 (distributed last time) is still due 5pm 2/2.

Today we finish our analysis of the "sink-to-merge" heap construction
procedure used by heapsort (also known as "heapify" in some books),
showing it is linear time.  We'll also compare the sorting methods
(quicksort, mergesort, heapsort) as promised last time.  In particular
we'll look at the "extra space" required by each method.

Continuing with notes:     24PriorityQueues.pdf (start at page 30)
Also, sorting animations:  www.sorting-algorithms.com/

We'll also go on to sketch a priority queue application developed by
the book: event-driven simulation.  The following commands exercise
the particle collision system developed by the textbook:

   cd /home/cs323000/share/book
   export CLASSPATH='*:.'
   java CollisionSystem 100
   java CollisionSystem < brownian.txt
   java CollisionSystem < diffusion.txt

We'll sketch how this works, and in particular how a priority queue
helps.  The main insight is that we use a priority queue to keep track
of possible future collision events (a collision of two particles, or
of a particle and a wall).  An event has a future timestamp, so we
simply ask the (min-oriented) priority queue for the next event.  We
then "jump" to that time, simulate the event (modifying at most 2
particles) and then create new events for the modified particles, so
O(N) work per collision, with N particles.

The main ideas are sketched out in our book and slides, we won't have
time to go through all the code details in lecture.

Remark: there is a potential problem with the PQ filling up with a
large number of invalid event objects, but in practice this does not
seem to be a problem.