Maxheap version of a heappush

[coopers]

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

• gh-110067: Add maxheap version of heappush. #110068
• gh-110067: Make max heap methods public and add missing ones #130725

[encukou]

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]

Yes, I've still got this.

[tnightengale]

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

Anyone still working on it ?

[inwardtxt]

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.

[StanFromIreland]

This can be closed now. I will add some further documentation updates in a follow up.

[encukou]

You could reuse this issue.

[StanFromIreland]

I had already created #133530, apologies, it just seemed a bit messy to use this one since there is a lot of unrelated comments.

[encukou]

That works too, especially if the changes aren't all related to max-heaps. (But, I wouldn't close before adding the link to the follow-up.)

@rhettinger: Please feel free to reopen if you want (us) to rework or remove the feature. There's time for than until July 28.