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.

classification
Title: Add Maxheap version of a heappush into heapq module
Type: enhancement Stage: resolved
Components: Library (Lib) Versions:
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: della, rhettinger, veerkharerudresh
Priority: normal Keywords:

Created on 2020-11-02 06:29 by veerkharerudresh, last changed 2022-04-11 14:59 by admin. This issue is now closed.

Messages (3)
msg380184 - (view) Author: Rudresh Veerkhare (veerkharerudresh) * Date: 2020-11-02 06:29
Main functions required to implement Heap data structure are: 
function heappush - to push an element in Heap
function heappop - to pop an element from Heap

for implementing Minheap this functions are present in the module as : 
heappush - for adding element into Minheap
heappop - to pop an element from Minheap

for implementing Maxheap only one of this two required functions is present:
_heappop_max - to pop an element from Maxheap

I suggest adding a Maxheap version of heappush into heapq module.
_heappush_max - for adding an element into Maxheap.
msg380226 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2020-11-02 14:35
Only the minheap is in the public API.  The maxheap functions are only supposed to be used internally.

Thank you for the suggestion, but I think we should decline.
msg382474 - (view) Author: Matteo Dell'Amico (della) Date: 2020-12-04 11:07
Personally, I'd find a maxheap in the standard library helpful, and a quick Google search tells me I'm not alone.

I generally have to deal with numeric values, so I have these choices:
 - ugly code (e.g., `minus_distance, elem = heappop(heap)`, `distance = -minus_distance`)
 - slow code (e.g., wrapping heapq in a class)

Since most of maxheap is already implemented in the library, I wonder what is the rationale for not including it.

A couple of use cases for max-heap that I ran into:
 - maintaining k-nearest-neighbor structures (the farthest known one is at the top of the queue)
 - running median (requires both a minheap and a maxheap)
History
Date User Action Args
2022-04-11 14:59:37adminsetgithub: 86406
2020-12-04 11:07:14dellasetnosy: + della
messages: + msg382474
2020-11-02 14:35:20rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg380226

stage: resolved
2020-11-02 09:37:56xtreaksetnosy: + rhettinger
2020-11-02 06:29:44veerkharerudreshcreate