Make max heap functions public in heapq

The heapq module contains some private max-heap variants of its heap functions: _heapify_max, _heappop_max, _heapreplace_max. This exist to support the higher-level functions like merge(). I’d like the _max variants to be made public (remove the underscore prefix), and documented. This will make it easy for users to create and manipulate max heaps as well.

The current public heapq functions only work with min-heaps. Using them to create a max-heap requires either storing inverted values (i.e. -x, which only works for numbers), or using some kind of wrapper class to invert comparisons.

Several such solutions are discussed in the 12 year old Stack Overflow question What do I use for a max-heap implementation in Python?. The second most popular solution is to use the private *_max variant functions, which I would like to make public.

(inspired by looking at the MinHeap problem on @trey 's Python Morsels)

1 Like

@rhettinger What do you think? Looks like a sensible request. If there’s a good reason not to do this it would be nice to have it written up for posterity.

It was proposed and rejected several times.

Two of those (non-)discussions were just dismissed on the basis that it has been rejected in the past. The first request was rejected on the basis that people haven’t needed it, but if you do, just negate the values.

If it is as simple as just negating your (numeric only) values, then why do the heapq have max-heap code for internal use? Why doesn’t it just negate the values?

The issue keeps coming up on the bug tracker, and on Stackoverflow:

and on PyPI, blog posts and more:

https://www.bing.com/search?q=python+maxheap

If the max heap code didn’t already exist, I could understand the reluctance to add it, but it does exist and it is already in use.

8 Likes

Indeed. I note it was mentioned by both the reporter and the responding developer on subsequent reports that this was brought up many times in the past and rejected, but the rationale given on the very first issue for rejecting it was that there hadn’t been “significant demonstrated need”, to which the original user did reply but was never responded to.

Certainly, there may be a compelling reason for rejecting this, but if so it should at least be stated and publicly documented, given the amount of interest and requests.

3 Likes

The next steps are to create an issue and a PR. Please link to both here.

We can do this. Much of the code is already there.

Mostly when this has come up before, it was usually a curiosity question, “I see a misheap, why isn’t there a maxheap?”. There wasn’t much in the way of actual needs other than being given this as a homework problem or coding challenge. That said, I’ve had some use cases and would like it if the functionality were exposed.

I’ll work on it soonish.

6 Likes