[Python-ideas] Heap data type

[Daniel Stutzbach]

On Sat, Apr 18, 2009 at 7:43 AM, Aahz <aahz at pythoncraft.com> wrote:

> +1 -- I recently did a short presentation on Big O notation and Python
> containers, and heapq looked remarkably ugly.
>

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.

I've implemented a couple of heaps for Python over the years:

1.
http://svn.python.org/view/sandbox/trunk/collections/pairing_heap.py?view=markup&pathrev=40887
(checked into the Sandbox... 5 years ago! I think I also have a C
reimplementation somewhere)

If you don't care about altering the priority, then the interface is more or
less like Facundo described.

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.


2. HeapDict.  http://pypi.python.org/pypi/HeapDict

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.

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. ;-)

--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20090418/2eaa31ce/attachment.html>