HEAP/priority queue

[Courageous]

> Could someone explain to a naive programmer here what the use of that
> lovely structure is?  I understand what is going on, just not why...

A heap priority queue has the property such that the elements
can be inserted and pulled out in a user-defined order in O(log N)
time. So, for example:

heap.push(7)
heap.push(3)
heap.push(9)
heap.push(2)

would be popped()

as 2,3,7,9

Obviously such a data structure is only needed when appending
onto the end all the time isn't possible (otherwise you'd
just use something like a fifo, both pushing and popping in
O(1)).

My application involves scheduling tasks to be time-sliced at
absolute simulation times (as opposed to real times). The-
simulator is sort of a melding of a full thread scheduling
(care of Mr. Tismer's continuation system), combined with
discrete event-based simulation, with events (and predicates
resolving from those events) having the ability to impact
the time slicing of various procedures in the system.

I'll probably eventually head to a native implementation for
pqueues, but not for a while (push/pop operations are
somewhere near 7th in the list of where all execution time
is going, so not really high on my own pqueue, yet).


C/