[Python-Dev] Priority queue (binary heap) python code

[Kevin O'Connor]

On Mon, Jun 24, 2002 at 11:09:32PM -0500, Skip Montanaro wrote:
> I don't know how efficient it would be, but I usually think that most
> applications have a small, fixed set of possible priorities, like ("low",
> "medium", "high") or ("info", "warning", "error", "fatal").  In this sort of
> situation my initial inclination would be to implement a dict of Queue
> instances which corresponds to the fixed set of priorities, something like:

Hi Skip,

The application I had in mind stored between 100,000-1,000,000 objects with
priorities between 0-150.  I found that moving from bisect to a heap
improved performance of the entire program by about 25%.

>It will also work if for some reason you want
> to queue up objects for which __cmp__ doesn't make sense.

I just assumed the user would use the (priority, data) tuple trick at the
start (it does make the algorithm simpler).  In a way, the code is very
similar to the way the bisect module is implemented.

-Kevin

-- 
 ------------------------------------------------------------------------
 | Kevin O'Connor                     "BTW, IMHO we need a FAQ for      |
 | kevin@koconnor.net                  'IMHO', 'FAQ', 'BTW', etc. !"    |
 ------------------------------------------------------------------------