[Python-Dev] Status of pairing_heap.py?

[Josiah Carlson]

"Paul Chiusano" <paul.chiusano at gmail.com> wrote:
> 
> > It is not required.  If you are careful, you can implement a pairing
> > heap with a structure combining a dictionary and list.
> 
> That's interesting. Can you give an overview of how you can do that? I
> can't really picture it. You can support all the pairing heap
> operations with the same complexity guarantees? Do you mean a linked
> list here or an array?

I mean a Python list.  The trick is to implement a sequence API that
keeps track of the position of any 'pair'.  That is, ph[posn] will
return a 'pair' object, but when you perform ph[posn] = pair, you also
update a mapping; ph.mapping[pair.value] = posn .  With a few other bits,
one can use heapq directly and get all of the features of the pairing
heap API without keeping an explicit tree with links, etc.

In terms of running time, adjust_key, delete, and extract(0) are all
O(logn), meld is O(min(n+m, mlog(n+m))), empty and peek are O(1), values
is O(n), and extract_all is O(nlogn) but uses list.sort() rather than
repeatedly pulling from the heap (heapq's documentation suggests this is
faster in terms of comparisions, but likely very much faster in terms of
actual running time).

Attached is a sample implementation using this method with a small test
example.  It may or may not use less memory than the sandbox
pairing_heap.py, and using bare lists rather than pairs may result in
less memory overall (if there exists a list "free list"), but this
should give you something to start with.

 - Josiah

> Paul
> 
> On 11/4/06, Josiah Carlson <jcarlson at uci.edu> wrote:
> >
> > "Martin v. Löwis" <martin at v.loewis.de> wrote:
> > > Paul Chiusano schrieb:
> > > > To support this, the insert method needs to return a reference to an
> > > > object which I can then pass to adjust_key() and delete() methods.
> > > > It's extremely difficult to have this functionality with array-based
> > > > heaps because the index of an item in the array changes as items are
> > > > inserted and removed.
> > >
> > > I see.
> >
> > It is not required.  If you are careful, you can implement a pairing
> > heap with a structure combining a dictionary and list.  It requires that
> > all values be unique and hashable, but it is possible (I developed one
> > for a commercial project).
> >
> > If other people find the need for it, I could rewrite it (can't release
> > the closed source).  It would use far less memory than the pairing heap
> > implementation provided in the sandbox, and could be converted to C if
> > desired and/or required.  On the other hand, I've found the pure Python
> > version to be fast enough for most things I've needed it for.
> >
> >  - Josiah
> >
> >
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pair_heap.py
Type: application/octet-stream
Size: 5377 bytes
Desc: not available
Url : http://mail.python.org/pipermail/python-dev/attachments/20061105/62f57d3a/attachment.obj