This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Title: Add unique option to heapq functions
Type: enhancement Stage: resolved
Components: Versions: Python 3.4
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: iritkatriel, pitrou, rhettinger, serhiy.storchaka
Priority: low Keywords:

Created on 2013-06-17 14:44 by pitrou, last changed 2022-04-11 14:57 by admin. This issue is now closed.

Messages (4)
msg191341 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-06-17 14:44
In one application, I would like to use a heap as an allocation pool. I also want to check that a given value isn't released twice, therefore that the heap contains unique values. My use case would be solved nicely if heappush() took an optional "unique=False" parameter.

Note that I haven't checked if doing so is possible while maintaining the O(log n) complexity :-)
msg191371 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-06-17 20:05
No, it's impossible without additional structure. And with a set it is trivial.

def uniqueheappush(heap, inheap, item):
    if id(item) in inheap:
        return False
    heappush(heap, item)
    return True

def uniqueheappop(heap, inheap):
    item = heappop(heap, inheap)
    return item

I recomend reject this issue.
msg191372 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-06-17 20:06
> No, it's impossible without additional structure. And with a set it is trivial.

Yeah, I wanted to avoid the memory overhead of a set.
msg415724 - (view) Author: Irit Katriel (iritkatriel) * (Python committer) Date: 2022-03-21 23:10
I would dedup when extracting items from the queue, because it is trivial to find duplicates then. It can be done with a simple wrapper, without any changes to the queue.
Date User Action Args
2022-04-11 14:57:47adminsetgithub: 62441
2022-03-24 04:32:51rhettingersetstatus: open -> closed
resolution: rejected
stage: resolved
2022-03-21 23:10:41iritkatrielsetnosy: + iritkatriel
messages: + msg415724
2013-06-17 20:06:30pitrousetmessages: + msg191372
2013-06-17 20:05:02serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg191371
2013-06-17 14:44:02pitroucreate