Allow heap removal at an arbitrary position, or a replacement with a new (or modified) object.

Feature or enhancement

Proposal:

Currently, if an object on a heap is modified, it is necessary to run heapq.heapify() to restore the heap property.
As an example, take a priority queue with objects that have a priority propety.

# removing an object from the heap
del heap[heap.index(myobj)]
heapq.heapify(heap)

# changing an object's priority
myobj.priority = new_priority
heapq.heapify(heap)

Instead, it would be useful, if an object's index is known, to be able to remove, modify, or replace it in O(log n) time:

# removing an object
heapq.heapremove(heap, heap.index(myobject))

# updating its priority:
myobject.priority = new_priority
i = heap.index(myobject)
heapq.heapremove(heap, i, replacement=myobject)

While finding an object in the heap is a an O(n) operation, it need not invoke the all important __lt__ operator
and reordering a heap, when a single object changes, can be done with O(logN) comparisons.

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response

Linked PRs

I'm just starting to work through this proposal by looking at other APIs and implementations:

https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
https://en.cppreference.com/w/cpp/container/priority_queue
https://pkg.go.dev/container/heap
https://docs.rs/priority-queue/latest/priority_queue/priority_queue/struct.PriorityQueue.html

I'm just starting to work through this proposal by looking at other APIs and implementations:

Interesting. In the PR I mention that im open to suggestions about naming, etc.
I see that golang has Fix and Remove, which are separate functions for doing what my proposed heapremove can do with an optional arg. I guess that is pretty clean.
But maybe we can move the discussion to the PR?

I've worked through a bunch of use cases and looked at several API variants. The most Pythonic API I've found is to accept a value to be removed rather than an index:

from heapq import heapify
from operator import indexOf

def heapremove(heap, item, *, key=None):
    "Baseline unoptimized version to specify the desired semantics."
    i = heap.index(item) if key is None else indexOf(map(key, heap), item)
    result = heap.pop(i)
    heapify(heap)
    return result

The key function is provided to support record types in a priority queue. Consider for example a queue of Task objects defined by:

Task = namedtuple('Task', ('priority', 'name', 'timestamp', 'callback'))

Then a pending task can be removed with any of these:

heapremove(tasks, 'restart', key=attrgetter('name'))
heapremove(tasks, some_time, key=attrgetter('timestamp'))
heapremove(tasks, some_callback, key=attrgetter('callback'))
heapremove(tasks, some_task_instance)

A heapremove() implementation has three steps: search, remove, and heapify.

The search step is necessarily linear but you may be able to cut the number of comparisons in half. See: https://stackoverflow.com/questions/2372994/search-an-element-in-a-heap

The remove step can be made O(1) by swapping with the last element and then running a list.pop()

The heapify step is the one than can be significantly optimized by using _siftup() and _siftdown() to replace the linear time heapify() call.

That gives us:

def heapremove(heap, item, *, key=None):
    "Optimized version"
    i = heap.index(item) if key is None else indexOf(map(key, heap), item)
    if len(heap) == i + 1:
        return heap.pop()
    found_item = heap[i]
    repl_item = heap[i] = heap.pop() 
    if repl_item < found_item:
        _siftdown(heap, 0, i)
    else:
        _siftup(heap, i)
    return found_item

For now, we can skip heap_fix(). Removing a task and pushing its replacement will suffice:

old_task = heapremove(tasks, 'check_mail', key=attrgetter('name'))
new_task = old_task._replace(priority=5, timestamp=time.time())
heappush(tasks, new_task)

This approach gives the user control over the what gets updated and it doesn't make assumptions about whether a task entry is mutable.

Overall, I think a heapremove() is a good idea. On the one hand, it is just an optimization of what we can already do with the existing API and for small heaps it likely won't be much of an improvement in speed. On the other hand, it presents a new high level way of thinking about the problem, and it abstracts away a lot of thought about the best way to implement it.

The heapremove implementation you make is essentially the same I have in #112550 except:

that it doesn't do a find.
IMHO, it is up to the user to do that. The user may have other means of deriving the index, or may decide at he doesn't want to remove it after finding it. heaps work on lists and there are plenty of ways of finding a list member. We should use decomposable operations.
Interestingly, list.index doesn't have a key argument. Perhaps this is an opportunity to add a list.find here?? Then we could simply do heapremove(mylist, mylist.find(key=mykey)) Which IMO is a cleaner way to achieve the combined effect you are looking for.
You perform a comparison in the function and either siftup/siftdown, whereas my version has siftdown return the final index, to be passed to siftup. It results in the same total amount of comparisons, but it might be considered cleaner to have all the comparisons in the siftup/siftdown methods rather than scattered about in higher level functions. OTOH, my usage might invalidate some of the preconditions in the comments to those functions so it is probably best to do it your way.

I also don't quite get your objection to having a heapfix, since it is faster still than heapremove()+heappush() and trivially implemented as a subset of heapremove()

Please see #112550 for a fully tested implementation

I've modified #112550 to use the same "if repl_item < found_item" logic as your code.
however, heapfix() does not have the previous value to work with so it continues to use:

if i > 0:
    i = _siftdown(heap, 0, i)
_siftup(heap, i)

the i > 0 comparison is formally not needed but skips a comparison in that case.

Please make an update to incorporate the find logic. A user has no a priiori way of knowing where the index is (it moves as the heap updates) and the existing API is value oriented and not index oriented.

For now, we'll omit headfix. It does save a few cycles but most of the win is already in heapremove. We want as small of an API expansion as possible and doesn't want to make assumptions about an item being mutable (the norm is to use tuples) that drive a user toward a different implementation.

Final appeal, before I change things:

Adding the "find" complicates things:

My use case is walking through the list, examining the objects, optionally removing one. Now we have to add an "optional" flag, or raise a ValueError or something.
The C implementation will become more complex.
We have to test a more complicated API with more permutations and edge cases.

It really feels like finding an index in a list should not be part of this API since it is a completely independent problem
and easily decomposable into more primitive actions without any increased algorithmic complexity. I'd be happier adding
a separate heapindex() function with the signature you describe, which could have a python-only implementation.

If you don't agree, I'll do it the way you like. And I'll drop the heapfix. Seeing how jealously you protect this module, I won't be trying some of my other PRs, I'll leave them for my heapq_plus package :)

p.s. indexOf and countOf don't appear to conform to naming conventions.

@gvanrossum

Seeing how jealously you protect this module ...

That comment feels abusive, personal, and unprofessional. It feels like an attempt to bully a reviewer into accepting an API expansion that isn’t in harmony with the module. AFAICT, I’m the only one to have paid any attention to this feature request, to have devoted volunteer research time during the holiday, or made an effort to move this forward.

@gvanrossum
Do you have a preference for the high level value oriented API, a lower level index oriented API, or dropping the proposal altogether? I'm +0 on the first option, -1 on the second, and fine with the third.

In general, the heap structure isn't conducive to removing or updating arbitrary entries in a priority queue. In a module that is all about O(log n) updates, removing or updating entries both stand out as O(n) operations. Whether it is a good idea or not, people do occasionally want to do this. Right now, the best way to remove a task is a list.remove(task) followed by a heapify() call. This is further complicated because real-world tasks are often objects with multiple fields, so task removal entails searching for a particular field such as a specific callback or task id.

By adding a new function, the work load can be reduced a bit. The search step would still be O(n) but the heapify step can be focused to a single siftup or siftdown step.

With a high level value oriented API, removing a task would look like this:

heapremove(tasks, 'check_mail', key=attrgetter('name'))

With a low level index oriented API, removing a task would look like this:

for i, task in enumerate(tasks):
    if tasks.name == 'check_mail':
        break
else:
    raise ValueError('task not found')
heapremove(tasks, i)

With the current API, removing a task looks like this:

for i, task in enumerate(tasks):
    if tasks.name == 'check_mail':
        break
else:
    raise ValueError('task not found')
del tasks[i]
heapify(tasks)

@gvanrossum

@gvanrossum
Do you have a preference for the high level value oriented API, a lower level index oriented API, or dropping the proposal altogether? I'm +0 on the first option, -1 on the second, and fine with the third.

Raymond. Stop calling me out whenever there's an issue. If you need to appeal to a higher authority, it's the SC, not me.

Seeing how jealously you protect this module ...

That comment feels abusive, personal, and unprofessional. It feels like an attempt to bully a reviewer into accepting an API expansion that isn’t in harmony with the module. AFAICT, I’m the only one to have paid any attention to this feature request, to have devoted volunteer research time during the holiday, or made an effort to move this forward.

Sorry that was not my intent, it was intended in good humour, seeing that we know each other from old times. On the contrary I quite admire careful shepherding of this piece of code. My apologies.

Since the entire heap*() api is a low level one, operating explicitly on lists, where even list[0] is the recommended way of getting a peek at the highest priority object, a remove operation which doesn't use the list index operator seems just a bit out of place, and unusually high-level. If the search is combined with it, it forces the operator into adopting a single pattern. He can no longer, for example, do:

for i, item in enumerate(heap.reversed()):  # my target is known to be low priority
   if should_remove(item):
       heapremove(heap, i)
       return item
 else:
     return None

Since internally, the removal does use the index, having a built-in search operation which just is a preamble to
produce that index seems like an overdesign of the api.

Just to clarify, in case I managed to somehow muddle the point I'm trying to make.

# high level api
def heapremove_high(heap, item, *, key=None):
    # raises ValueError if item not found
    index = heap.index(item) if key is not None else indexOf(map(heap, key), value)
    return heapremove_low(heap, index)

def heapremove_low(heap, index):
    # raises indexerror if index not found
    # dummy version:
    result = heap[index]
    del heap[index]
    heapify(heap)
    return index

The high level api just sticks a convenient search in front. but without the low level api, the user is forced into
using the particular search pattern built into the high level api.

Anyway, sorry for sounding offensive, still awaiting your decision.

Oh, and since you mentioned that there is no way to know the index of an object,
I do in fact have versions of the heap*() function which accept a callable which can update an index map of the items in the queue for each operation, or even, update an attribute within each entry, roughly:

def heappush(heap: list[Any], item: Any, *, map: Optional[Callable[(Any, int)]] = None):
    """push an item onto the list, optionally calling a callable for an item and its new index in the heap for any item which changes position"""
    
heap = []
heapmap = {}
heappush(heap, "foo", map=lambda k, i: heapmap[k] = i)
heappush(heap, "bar", map=lambda k, i: heapmap[k] = i)
assert heap == ["bar", "foo"]
assert heapmap == {"foo": 1, "bar": 0}

For cases where you expect a lot of removals/updates, this will remove the O(n) factor from the equation entirely.

But that's a more radical change and one I'm not pushing into the stdlib.

Just occurred to me that I can just provide two functions, heapremove_index being a low-level one easily implementable in C and heapremove() with the high level api with a .py implementation on top. I'll update the pr presently, also removing heapfix

@gvanrossum

@gvanrossum
It wasn’t authority I was looking for. It was your instinct for Pythonic API design and a good user experience. If you’re not interested in giving your insights and guidance, sorry to have bugged you.

Sorry that was not my intent, it was intended in good humour, seeing that we know each other from old times. On the contrary I quite admire careful shepherding of this piece of code. My apologies.

No worries. We're good.

I'm going to have to ghost you for week though. Right now, I'm on a cruise ship with bad connectivity when not in port.

I've updated the PR, with a heapremove_index() implemented in .py and .c. I'm also okay with making it unofficial, adding an underscore, if that is what you like. the search itself, though, does not, IMO, benefit from being implemented in C.
Cheers, and enjoy your cruise.

Fix some grammar mistakes in comments in _pylong.py

Navigation Menu

Repository navigation

Allow heap removal at an arbitrary position, or a replacement with a new (or modified) object. #112498

Feature or enhancement

Proposal:

Has this already been discussed elsewhere?

Links to previous discussion of this feature:

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Allow heap removal at an arbitrary position, or a replacement with a new (or modified) object. #112498

Description

Feature or enhancement

Proposal:

Has this already been discussed elsewhere?

Links to previous discussion of this feature:

Linked PRs

Activity

rhettinger commented on Nov 29, 2023

kristjanvalur commented on Nov 29, 2023

rhettinger commented on Jan 2, 2024

kristjanvalur commented on Jan 2, 2024

kristjanvalur commented on Jan 2, 2024

rhettinger commented on Jan 2, 2024

kristjanvalur commented on Jan 2, 2024

rhettinger commented on Jan 3, 2024

gvanrossum commented on Jan 3, 2024

kristjanvalur commented on Jan 3, 2024

kristjanvalur commented on Jan 3, 2024

kristjanvalur commented on Jan 3, 2024

rhettinger commented on Jan 3, 2024

rhettinger commented on Jan 3, 2024

kristjanvalur commented on Jan 4, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions