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

[kristjanvalur]

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

• gh-112498: Allow removal/update of an object at an arbitary position in a a heap #112497
• GH-112498 Add heapremove and heapfix #112550

[rhettinger]

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

[kristjanvalur]

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?

[rhettinger]

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.

[kristjanvalur]

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

1. 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.
2. 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

[kristjanvalur]

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.

[rhettinger]

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.

[kristjanvalur]

Final appeal, before I change things:

Adding the "find" complicates things:

1. 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.
2. The C implementation will become more complex.
3. 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.

[rhettinger]

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.