As it turns out, there actually is a wrapper class in the stdlib which encapsulates heapq: queue.PriorityQueue, at least for the most part. Although its intention is not to be a wrapper class for heapq, it is one by nature. But for the sake of its actual purpose, threading, it comes with overhead. This overhead is actually quite noticeable, but not so bad that I would say it is unusable.
It also lacks several features, namely: - No equivalent for heapify i.e. no constructor accepting iterable arguments (you *could* heapify first, then queue.put the items to ensure it is O(n)). - No equivalent for peek, pushpop, or replace i.e. expensive push + pop variants need to be used instead. Despite these flaws, the queue.PriorityQueue is quite usable in many cases and offers a wrapper class, which is clearly for many (but not everyone) quite a nice plus, potentially worth the threading overhead. >From this, we can also see that a Heap class is actually not the correct base >class, but rather that a Queue is probably more appropriate, unless the >underlying list is wanted for some reason (for most cases, I would assume it >is not, but revealing it should not be a problem either). I can also imagine that optimizations for heapq are possible if moved this way. Currently heapq accepts any MutableSequence, but this comes with some cost I think. If it were a part of the builtin list, or better yet made into its own class, and then written in C, I would assume it would be faster. I think it is safe to say that most people do not use heapq with anything other than lists. In fact I think it is safe to say that most people do not even care about the underlying list when using heapq. The list is more of an implementation detail than anything. A big issue that I see with this suggestion, however, is that it would be confusing to lack or include the peek, pushpop, and replace methods. If they are missing, users will be confused when comparing it to heapq. If they are included, the inconsistency with the queue module will be confusing. I suppose there wouldn't be any harm with adding them to the queue module, but one might question whether or not such is worth it. I can see the exact semantics of peek, pushpop, and replace being confusing in the context of threading. Though a non-issue, the name "pushpop" also doesn't align with queue, and I think "putget" does not sound so nice. Another issue is where would these belong. We already have the queue module, so it may be easy for users to get confused seeing the two. Should it go in collections then? Should it stay in heapq? Although I don't see it happening, I would prefer to have the others inside of concurrent.queue and have queue dedicated to non-concurrent base classes. But of course this would destroy the backwards compatibility of queue, so I can't see that happening. Another issue I see is that queue is meant to support concurrency, and thus has additional features such as queue.task_done(). Although a base Queue class does not necessarily need to implement such, the fact that queue.PriorityQueue has methods such as these makes it confusing to users not interested in concurrency. _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/754MNV25IGALLDLUOV5HZQ3ASKTB5CNU/ Code of Conduct: http://python.org/psf/codeofconduct/
