Repository navigation
Allow heap removal at an arbitrary position, or a replacement with a new (or modified) object. #112498
Description
Activity
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.htmlI'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 hasFixandRemove, 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 resultThe 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_itemFor 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
heapremoveimplementation 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.indexdoesn't have akeyargument. Perhaps this is an opportunity to add alist.findhere?? Then we could simply doheapremove(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
siftdownreturn the final index, to be passed tosiftup. 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 thanheapremove()+heappush()and trivially implemented as a subset ofheapremove()Please see #112550 for a fully tested implementation
- that it doesn't do a find.
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 > 0comparison 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
ValueErroror 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 separateheapindex()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 myheapq_pluspackage :)p.s.
indexOfandcountOfdon't appear to conform to naming conventions.- 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
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 aheapify()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
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, aremoveoperation 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
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.
Reacted by Kristján Valur JónssonI'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.- added a commit that references this issue
on Jan 4, 2024
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.
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:
While finding an object in the heap is a an O(n) operation, it need not invoke the all important
__lt__operatorand 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