<div class="gmail_quote">On Sat, Apr 18, 2009 at 7:43 AM, Aahz <span dir="ltr"><<a href="mailto:aahz@pythoncraft.com">aahz@pythoncraft.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
+1 -- I recently did a short presentation on Big O notation and Python<br>
containers, and heapq looked remarkably ugly.<br>
<font color="#888888"></font></blockquote></div><br>Another issue with heapq is that it does not support modifying the priority of an existing element (usually called the "decrease_key" operation in textbooks).  The hard part of incrementing decrease_key is that somehow the object in the heap needs to know its current position, else you have to do an expensive linear search to find the object's current position.<br>
<br>I've implemented a couple of heaps for Python over the years:<br><br>1. <a href="http://svn.python.org/view/sandbox/trunk/collections/pairing_heap.py?view=markup&pathrev=40887">http://svn.python.org/view/sandbox/trunk/collections/pairing_heap.py?view=markup&pathrev=40887</a><br>

(checked into the Sandbox... 5 years ago! I think I also have a C reimplementation somewhere)<br><br>If you don't care about altering the priority, then the interface is more or less like Facundo described.<br><br>To keep track of the positions, insert operations return a wrapper around each object.  The user needs to keep track of the wrapper and pass it to the adjust_key() method if they want to change the priority of the object later.  <br>
<br><br>2. HeapDict.  <a href="http://pypi.python.org/pypi/HeapDict">http://pypi.python.org/pypi/HeapDict</a><br><br>Looks, act, and quacks like a dict/MutableMapping, except popitem() returns the item with the lowest value instead of a random item.  Also, there's a peekitem() method to examine that item without removing it.  Since the interface is familiar, it's super-easy to use without having to look up the names of the methods whenever you need to use a heap.  <br>
<br>The downside is that you can't add the same element into the heap twice (just like you can't have the same key in a dictionary twice).  Personally I've only inserted the same element more than once when doing toy examples with integers, so for me at least that's no great loss. ;-)<br>
<blockquote style="margin: 1.5em 0pt;">--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</blockquote>