Skip to content

Maxheap version of a heappush #110067

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
coopers opened this issue Sep 29, 2023 · 5 comments
Open

Maxheap version of a heappush #110067

coopers opened this issue Sep 29, 2023 · 5 comments
Assignees
Labels
extension-modules C modules in the Modules dir stdlib Python modules in the Lib dir type-feature A feature request or enhancement

Comments

@coopers
Copy link

coopers commented Sep 29, 2023

Feature or enhancement

Proposal:

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

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

conversation on making max heap functions public

Linked PRs

@coopers coopers added the type-feature A feature request or enhancement label Sep 29, 2023
@iritkatriel iritkatriel added the stdlib Python modules in the Lib dir label Nov 27, 2023
@encukou
Copy link
Member

encukou commented Mar 4, 2024

Functions with a leading underscore are private -- i.e. _heappush_max should not be used outside heapq itself. It should be named without an underscore, and it would also need documentation and tests.

Raymond said he's working on public maxheap functions. If you'd like to work on this, perhaps ask if he's still on it.

@rhettinger
Copy link
Contributor

Yes, I've still got this.

@tnightengale
Copy link

@rhettinger 👋 Would you like any help on this? Recently I reached for a max-heap in python and was surprised it didn't exist. Saw this thread and wondered if this is still on anyone's radar, since it was not released with 3.13.

@Teut2711
Copy link

Anyone still working on it ?

@inwardtxt
Copy link

Is there an update on this, or why it wasn't added @rhettinger ?
You said "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.", but there is no sign of public max heap functions or even a private _heappush_max.
You also said "There wasn’t much in the way of actual needs other than being given this as a homework problem or coding challenge.". If you are looking for a reason to add it then here it is:
Currently the intended way of creating a max heap from an unsorted list of ints is to iterate through the entire list and generate the negative version of the int. Then when you are popping from the simulated max heap, you negate the int again. Now suppose you need to simulate a max heap from strings, using the same logic, the "intended" way would be iterate through your list and wrap each string in an object that overrides the less than operator. That is extremely unpythonic.
Additionally, the intended method will cause you to iterate through the list while inverting the sign of each element, which takes O(n) time, and then you will create the "max heap" with this list in O(n) time. It is completely unnecessary to have the intended method for a max heap be O(2n) and a min heap is O(n).
Currently, the actual simplest method is to implement your own _heappush_max function like the suggested addition, and use the private max heap functions. If the simplest method is unintended, then it should probably change, especially when the change takes 1 second.

penguinuwu added a commit to penguinuwu/fictional-system that referenced this issue Feb 17, 2025
also its been 3 years since maxheap was promised...
python/cpython#110067
@picnixz picnixz added the extension-modules C modules in the Modules dir label Mar 1, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
extension-modules C modules in the Modules dir stdlib Python modules in the Lib dir type-feature A feature request or enhancement
Projects
None yet
Development

No branches or pull requests

8 participants