# Make max heap functions public in heapq

**URL:** <https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944>\
**Category:** Ideas\
**Created:** [June 30, 2022, 3:56pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944 "2022-06-30T15:56:35Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![adamchainz](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/adamchainz/32/2003_2.png) [@adamchainz](https://discuss.python.org/u/adamchainz)\
**Post date:** [June 30, 2022, 3:56pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/1 "2022-06-30T15:56:35Z")

</div>

[The `heapq` module](https://docs.python.org/3/library/heapq.html) 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?](https://stackoverflow.com/questions/2501457/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)

---

<div class="post-metadata">

**Author:** ![guido](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/guido/32/21_2.png) [@guido](https://discuss.python.org/u/guido)\
**Post date:** [June 30, 2022, 4:10pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/2 "2022-06-30T16:10:21Z")

</div>

@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.

---

<div class="post-metadata">

**Author:** ![storchaka](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/storchaka/32/217_2.png) [@storchaka](https://discuss.python.org/u/storchaka)\
**Post date:** [July 1, 2022, 5:07am UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/3 "2022-07-01T05:07:47Z")

</div>

It was proposed and rejected several times.

> <https://github.com/python/cpython/issues/71482>
>
> BPO | \[27295\](https://bugs.python.org/issue27295)
> \--- | :---
> Nosy | @rhettinger,… @CrazyPython
> 
> \<sup\>\*Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.\*\</sup\>
> 
> \<details\>\<summary\>Show more details\</summary\>\<p\>
> 
> GitHub fields:
> \`\`\`python
> assignee = None
> closed\_at = \<Date 2016-06-11.20:39:10.571\>
> created\_at = \<Date 2016-06-11.13:49:52.534\>
> labels = \['type-feature', 'library'\]
> title = 'heaps library does not have support for max heap'
> updated\_at = \<Date 2016-06-12.12:36:14.552\>
> user = 'https://github.com/CrazyPython'
> \`\`\`
> 
> bugs.python.org fields:
> \`\`\`python
> activity = \<Date 2016-06-12.12:36:14.552\>
> actor = 'James.Lu'
> assignee = 'none'
> closed = True
> closed\_date = \<Date 2016-06-11.20:39:10.571\>
> closer = 'rhettinger'
> components = \['Library (Lib)'\]
> creation = \<Date 2016-06-11.13:49:52.534\>
> creator = 'James.Lu'
> dependencies = \[\]
> files = \[\]
> hgrepos = \[\]
> issue\_num = 27295
> keywords = \[\]
> message\_count = 3.0
> messages = \['268211', '268269', '268370'\]
> nosy\_count = 3.0
> nosy\_names = \['rhettinger', 'stutzbach', 'James.Lu'\]
> pr\_nums = \[\]
> priority = 'normal'
> resolution = 'rejected'
> stage = None
> status = 'closed'
> superseder = None
> type = 'enhancement'
> url = 'https://bugs.python.org/issue27295'
> versions = \['Python 3.6'\]
> \`\`\`
> 
> \</p\>\</details\>

> <https://github.com/python/cpython/issues/86406>
>
> BPO | \[42240\](https://bugs.python.org/issue42240)
> \--- | :---
> Nosy | @rhettinger,… @RudreshVeerkhare
> 
> \<sup\>\*Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.\*\</sup\>
> 
> \<details\>\<summary\>Show more details\</summary\>\<p\>
> 
> GitHub fields:
> \`\`\`python
> assignee = None
> closed\_at = \<Date 2020-11-02.14:35:20.005\>
> created\_at = \<Date 2020-11-02.06:29:44.583\>
> labels = \['type-feature', 'library'\]
> title = 'Add Maxheap version of a heappush into heapq module'
> updated\_at = \<Date 2020-12-04.11:07:14.701\>
> user = 'https://github.com/RudreshVeerkhare'
> \`\`\`
> 
> bugs.python.org fields:
> \`\`\`python
> activity = \<Date 2020-12-04.11:07:14.701\>
> actor = 'della'
> assignee = 'none'
> closed = True
> closed\_date = \<Date 2020-11-02.14:35:20.005\>
> closer = 'rhettinger'
> components = \['Library (Lib)'\]
> creation = \<Date 2020-11-02.06:29:44.583\>
> creator = 'veerkharerudresh'
> dependencies = \[\]
> files = \[\]
> hgrepos = \[\]
> issue\_num = 42240
> keywords = \[\]
> message\_count = 3.0
> messages = \['380184', '380226', '382474'\]
> nosy\_count = 3.0
> nosy\_names = \['rhettinger', 'della', 'veerkharerudresh'\]
> pr\_nums = \[\]
> priority = 'normal'
> resolution = 'rejected'
> stage = 'resolved'
> status = 'closed'
> superseder = None
> type = 'enhancement'
> url = 'https://bugs.python.org/issue42240'
> versions = \[\]
> \`\`\`
> 
> \</p\>\</details\>

> <https://github.com/python/cpython/issues/89107>
>
> BPO | \[44944\](https://bugs.python.org/issue44944)
> \--- | :---
> Nosy | @ericvsmith,… @yatharthmathur
> PRs | \<li\>python/cpython#27806\</li\>\<li\>python/cpython#27807\</li\>
> 
> \<sup\>\*Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.\*\</sup\>
> 
> \<details\>\<summary\>Show more details\</summary\>\<p\>
> 
> GitHub fields:
> \`\`\`python
> assignee = None
> closed\_at = \<Date 2021-08-19.03:37:18.267\>
> created\_at = \<Date 2021-08-18.04:12:48.746\>
> labels = \['type-feature', 'library', '3.11'\]
> title = "Addition of \_heappush\_max method to complete the max heap implementation in Python's heapq module"
> updated\_at = \<Date 2021-08-19.03:37:18.266\>
> user = 'https://github.com/yatharthmathur'
> \`\`\`
> 
> bugs.python.org fields:
> \`\`\`python
> activity = \<Date 2021-08-19.03:37:18.266\>
> actor = 'rhettinger'
> assignee = 'none'
> closed = True
> closed\_date = \<Date 2021-08-19.03:37:18.267\>
> closer = 'rhettinger'
> components = \['Library (Lib)'\]
> creation = \<Date 2021-08-18.04:12:48.746\>
> creator = 'yatharthmathur'
> dependencies = \[\]
> files = \[\]
> hgrepos = \[\]
> issue\_num = 44944
> keywords = \['patch'\]
> message\_count = 1.0
> messages = \['399846'\]
> nosy\_count = 2.0
> nosy\_names = \['eric.smith', 'yatharthmathur'\]
> pr\_nums = \['27806', '27807'\]
> priority = 'normal'
> resolution = 'duplicate'
> stage = 'resolved'
> status = 'closed'
> superseder = None
> type = 'enhancement'
> url = 'https://bugs.python.org/issue44944'
> versions = \['Python 3.11'\]
> \`\`\`
> 
> \</p\>\</details\>

---

<div class="post-metadata">

**Author:** ![steven.daprano](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/steven.daprano/32/1083_2.png) [@steven.daprano](https://discuss.python.org/u/steven.daprano)\
**Post date:** [July 2, 2022, 2:19am UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/4 "2022-07-02T02:19:36Z")

</div>

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:

> <https://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python>

> <https://stackoverflow.com/questions/12681772/pop-max-value-from-a-heapq-python-is-there-a-max-heap-in-python>

> <https://stackoverflow.com/questions/3950368/min-heap-is-but-is-a-max-heap-module-defined-in-python>

> <https://stackoverflow.com/questions/33024215/built-in-max-heap-api-in-python>

and on PyPI, blog posts and more:

[https://www.bing.com/search?q=python+maxheap](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.

---

<div class="post-metadata">

**Author:** ![CAM-Gerlach](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/cam-gerlach/32/3688_2.png) [@CAM-Gerlach](https://discuss.python.org/u/CAM-Gerlach)\
**Post date:** [July 2, 2022, 2:35pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/5 "2022-07-02T14:35:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![guido](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/guido/32/21_2.png) [@guido](https://discuss.python.org/u/guido)\
**Post date:** [July 2, 2022, 7:10pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/6 "2022-07-02T19:10:09Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![rhettinger](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rhettinger/32/1129_2.png) [@rhettinger](https://discuss.python.org/u/rhettinger)\
**Post date:** [July 9, 2022, 6:32am UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/7 "2022-07-09T06:32:11Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![coopers](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/coopers/32/14956_2.png) [@coopers](https://discuss.python.org/u/coopers)\
**Post date:** [September 29, 2023, 12:58am UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/8 "2023-09-29T00:58:25Z")

</div>

Does anyone want to see a max heap version of heappush?

```python
def _heappush_max(heap, item):
    """Maxheap version of a heappush."""
    heap.append(item)
    _siftdown_max(heap, 0, len(heap)-1)

```

---

<div class="post-metadata">

**Author:** ![rhettinger](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rhettinger/32/1129_2.png) [@rhettinger](https://discuss.python.org/u/rhettinger)\
**Post date:** [September 29, 2023, 2:39am UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/9 "2023-09-29T02:39:43Z")

</div>

I have a PR in process for making public maxheap functions across the board. It will go in for the next version of Python. It’s too late for 3.12.

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tczajka/32/17809_2.png) [@tczajka](https://discuss.python.org/u/tczajka)\
**Post date:** [February 11, 2024, 12:27pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/10 "2024-02-11T12:27:53Z")

</div>

Instead of creating a max version, wouldn’t it make more sense to add a `reverse=` and `key=` optional arguments, like you have with `sort`? This would allow you to have heaps based on any ordering you want.

---

<div class="post-metadata">

**Author:** ![blhsing](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/blhsing/32/25812_2.png) [@blhsing](https://discuss.python.org/u/blhsing)\
**Post date:** [February 20, 2024, 4:26am UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/11 "2024-02-20T04:26:10Z")

</div>

> [@rhettinger](#):
>
> There wasn’t much in the way of actual needs other than being given this as a homework problem or coding challenge.

A good use case for a max heap is mentioned in `heapq`’s [documentation](https://docs.python.org/3/library/heapq.html) itself:

> [@](#):
>
> a “max heap” is more common in texts because of its suitability for in-place sorting

As far as I know, in-place sorting with a max heap is the only way to sort an arbitrary list with _O(n log n)_ time complexity and _O(1)_ space complexity.

I recently posted a fairly lengthy answer to an old StackOverflow question with all the hoop-jumping workarounds only because the max heap functions aren’t exposed as public functions from `heapq`:

> <https://stackoverflow.com/questions/62329870/python-sort-in-constant-space-o1>

But on second thought, if in-place sorting is the only good use case for a max heap, then maybe instead of making max heap functions public we can make in-place sorting itself a public function in `heapq`.

---

<div class="post-metadata">

**Author:** ![EklipZgit](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/eklipzgit/32/18869_2.png) [@EklipZgit](https://discuss.python.org/u/EklipZgit)\
**Post date:** [March 28, 2024, 8:51pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/12 "2024-03-28T20:51:33Z")

</div>

Hey, I just want to point out that this seems like a big gap. “Just invert the values negatively” isn’t a great answer when you’re sorting complex objects with custom comparitors. What, I’m just supposed to invert my **gt** and **lt** methods in an expensive wrapper class? What if I’m trying to use the objects I put in the heap for other purposes? Other algorithms use heaps. What if I’m writing an A\*-like heuristic function (actually, I have a lot of these, hundreds and hundreds of lines of code of tens of implementations of variations on these for game AI) and need to maximize a heuristic? I have to take my heuristic val and invert it before putting it in the heap, resulting in a ton of overly complex (and computationally wasteful) conversion code, just to get the value back out and invert it again before doing all the other value comparisons that need to be done. I’m surprised more people aren’t complaining, I guess not that many people write complex heuristic searches in python?

I got sick of the overly complex and obtuse negation in my value functions (over 2x the amount of code is necessary because of missing max-heap, I need a heuristic func that produces the actual values for other things to use, and then a separate heuristic func that chains the output from the value func and inverts each property individually for the heap-based search), and started switching to use [heapq\_max · PyPI](https://pypi.org/project/heapq_max/) instead for much, much cleaner code for my (many) use cases where the search heuristic and value heuristic are the same, but it is so old (or inefficiently compiled?) that the performance is about 100% worse than the min-heap in heapq. I’ve tried [heap-class · PyPI](https://pypi.org/project/heap-class/0.9.0b1/) as well but its performance is even worse than that, for both min and max heaps.

I’m using python because I dont want to write C (nor figure out how to get my C compiled as fast as heapq is, as well as figuring out all the interop stuff…)

Please, just give us high performance max-heap methods from heapq ☹ it seems so strange for such an important core data structure from core algorithms to be completely missing.

---

<div class="post-metadata">

**Author:** ![dumbpotato](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dumbpotato/32/10305_2.png) [@dumbpotato](https://discuss.python.org/u/dumbpotato)\
**Post date:** [August 1, 2024, 1:33pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/13 "2024-08-01T13:33:32Z")

</div>

So has there been progress on this? Tried searching for the PR but only found [this](https://github.com/python/cpython/pull/102410) which was closed by @rhettinger saying he’ll raise another PR.

Also, perhaps I missed the link in the thread, but could someone link me to the Github issue for this(if it exists). Thanks!

---

<div class="post-metadata">

**Author:** ![prashanthbanda](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/prashanthbanda/32/23420_2.png) [@prashanthbanda](https://discuss.python.org/u/prashanthbanda)\
**Post date:** [October 16, 2024, 6:50pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/14 "2024-10-16T18:50:08Z")

</div>

Python 3.13 is released but there is no mention of max heap in it.

---

<div class="post-metadata">

**Author:** ![Stanfromireland](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/stanfromireland/32/10102_2.png) [@Stanfromireland](https://discuss.python.org/u/Stanfromireland)\
**Post date:** [March 1, 2025, 3:42pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/15 "2025-03-01T15:42:07Z")

</div>

I have opened [gh-110067: Make max heap methods public and add missing ones by StanFromIreland · Pull Request #130725 · python/cpython · GitHub](https://github.com/python/cpython/pull/130725) as Raymond has not opened his for quite a while.

---

<div class="post-metadata">

**Author:** ![Stanfromireland](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/stanfromireland/32/10102_2.png) [@Stanfromireland](https://discuss.python.org/u/Stanfromireland)\
**Post date:** [May 6, 2025, 5:31pm UTC](https://discuss.python.org/t/make-max-heap-functions-public-in-heapq/16944/16 "2025-05-06T17:31:00Z")

</div>

Implemented now:-)