Title: Add Heap (and DynamicHeap) classes to heapq module
Type: enhancement Stage: patch review
Components: Library (Lib) Versions: Python 3.4
Status: closed Resolution: duplicate
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: allyourcode, pitrou, r.david.murray, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2013-04-24 18:52 by allyourcode, last changed 2013-04-29 11:05 by rhettinger. This issue is now closed.

File name Uploaded Description Edit
heap.patch allyourcode, 2013-04-24 18:52 hg diff -r e0c0bcd > heap.patch review
heap2.diff rhettinger, 2013-04-29 10:36 Draft of Heap() class
Repositories containing patches
Messages (10)
msg187723 - (view) Author: Daniel Wong (allyourcode) * Date: 2013-04-24 18:52
heapq already provides a bunch of functions for manipulating lists that preserve (or create) a heap invariant. My change adds two classes for representing heaps. These classes ensure that operations that violate the heap invariant are not possible (through the public interface). The also allow customization via subclassing.
msg187749 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-04-24 22:22
msg187750 - (view) Author: Daniel Wong (allyourcode) * Date: 2013-04-24 23:27
Hey Serhiy,

Are you suggesting that I put my new classes in a new module and rename them? I think it'd be better to keep them in heapq, unless someone intended to add more classes to your proposed queue module, because heap functionality would be spread between two modules (heapq and queue).

One could argue that these classes could go in the collections module, but I think sticking to heapq is best.
msg187753 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2013-04-25 02:09
Serhiy is pointing you to an existing use of heapq in the stdlib.  I'm not quite sure what his intent is in pointing it out, though it *might* be to point out that heapq is a primitive, and PriorityQueue already implements a subclassable class using it.

I don't personally have any opinion either way on the utility of your proposed classes.  I've only ever used PriorityQueue once :)
msg187756 - (view) Author: Daniel Wong (allyourcode) * Date: 2013-04-25 05:37
Ah, Serhiy is pointing out that there's already a class named PriorityQueue in the queue module. I didn't know that exists.

Now that I've had a chance to look at it, queue.PriorityQueue is like my Heap class, but there are some interesting difference; moreover, I'm also proposing DynamicHeap, which is pretty different from PriorityQueue. Perhaps, I should find a way to augment PriorityQueue so that it supports the interesting features of DynamicHeap?
msg187863 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-04-26 15:03
queue.PriorityQueue is a locked class for use in multi-threaded code. That's like saying Queue is a good substitute for list :-)

OTOH, the proposed patch raises a lot of warning signs for me. I will wait for a decision on the feature's desirability before making a review.
msg187865 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-04-26 15:52
From my multilingual experience I can say that priority queue is very rarely used type of collections (but if it needed it is very usefull). On one hand, Python stdlib already contains one such type, and this type will be good enough in non-performance-critical applications. On other hand, a non-locked implementation using heapq is trivial (just encapsulate a list inside a class), no one will implement it wrong (if do not over-complicate the interface). I don't see the need for yet one priority queue. The presence of two very similar types in the stdlib will lead to confusion.
msg187894 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-04-27 08:22
See also rejected issue1162363.
msg188060 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-04-29 10:36
Daniel, I've already been in the process of adding a class to the heapq module and have done substantial work on it over the last few months.  I'll look at your code to see if there are any ideas that should be merged with it before I finish it up.

Am attaching my current draft for Heap().  A PriorityQueue() variant would also be added to 3.4.
msg188065 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-04-29 11:05
Daniel, I'm going to close this one so we can continue work in just a single tracker item:   

I'll see if anything in your code should be merged in to mine and will list you as a co-contributor when it all goes in.
Date User Action Args
2013-04-29 11:05:54rhettingersetmessages: - msg188062
2013-04-29 11:05:40rhettingersetmessages: + msg188065
2013-04-29 10:47:31rhettingersetmessages: - msg188061
2013-04-29 10:47:14rhettingersetstatus: open -> closed
resolution: duplicate
messages: + msg188062
2013-04-29 10:37:44rhettingersetmessages: + msg188061
2013-04-29 10:36:17rhettingersetfiles: + heap2.diff

messages: + msg188060
2013-04-29 10:28:27rhettingersetassignee: rhettinger
2013-04-27 08:22:05serhiy.storchakasetmessages: + msg187894
2013-04-26 15:52:39serhiy.storchakasetmessages: + msg187865
2013-04-26 15:03:13pitrousetnosy: + pitrou
messages: + msg187863
2013-04-25 05:37:41allyourcodesetmessages: + msg187756
2013-04-25 02:09:33r.david.murraysetnosy: + r.david.murray
messages: + msg187753
2013-04-24 23:27:43allyourcodesetmessages: + msg187750
2013-04-24 22:22:43serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg187749
2013-04-24 21:46:46pitrousetnosy: + rhettinger
stage: patch review

versions: + Python 3.4
2013-04-24 18:52:33allyourcodecreate