priority queue

[Courageous]

On Wed, 06 Jun 2001 06:41:55 GMT, "Nick Perkins" <nperkins7 at home.com> wrote:

>I need a priority queue, but I am not sure what kind I should use.  I will
>be doing insertions that will likely fall somewhere in the middle, and will
>only be removing from the front of the queue.  I expect insertions to
>out-number removals by about 2 or 3 to one.

Use a standard binary heap. It will do absolutely fine in all general
cases. Your other alternative is a fibonacci heap, which is optimized
for insert. I have the binary heap at:

http://www.sourceforge.net/projects/pythonic

Checkout the "pythonic" module. The adt submodule is what you
want. It also has a circular dequeue and a specialized python list
which supports O(1) head-push and tail-append.

The priority queue interface should be obvious. See test_pqueue.py
in the same directory.



C//