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
Support heapfix() and heapremove() APIs in heapq module #75369
Comments
I'd like to suggest a couple of utility methods for the heapq module which I think are useful:
Currently, the way to fix the heap after an arbitrary item has changed is to just call heapify() on the entire heap. This is inefficient because heapify() tries to perform _siftup() operation on half of the items of the heap to maintain the heap invariant. Doing this is unnecessary because we know exactly which element (or index) was changed and became out of place. With a heapfix() function, we can just "fix" the heap from that position.
Pretty much same as above. If you remove an item from an arbitrary index, you have to call heapify() to restore the heap invariant. Supporting these methods require minimal changes to the existing _siftup() and _siftdown() methods (basically just returning position values without changing any logic at all). I have a draft implementation which I've attached as a patch file here. If there's interest in this, I can write some tests and create a Github PR. Thanks! |
-1 I don't think this is the right way to use heaps. Also, I don't want to introduce any O(n) operations for fine-grained changes of a single element (part of the point of having a heap is to make fine-grained changes cheap). FWIW, it isn't common to change an element and then call heapify. Instead, the usual approach is either mark an entry as invalid or keep a pending deletion list or sets. |
Thanks, Raymond. I think it's fair comment, but I'm not sure which operation is O(n) though. FWIW, Go supports these operations (https://golang.org/pkg/container/heap/), so the usage is there. |
@rajath, I suspect Raymond may have been bamboozled because your suggested I thought about adding them years ago, but didn't find a _plausible_ use case: the index at which a specific heap item appears is pretty much senseless, and typically varies over a heap's lifetime. So how does the user know _which_ index to pass? A linear search over the underlying list to find the index of a specific heap item is probably unacceptable. The only hacks around that I could think of required a more complex kind of heap; e.g., restricting heap items to objects usable as dict keys, using a hidden dict to map heap items to their current index, and fiddling all the heap operations to keep that dict up to date. So, in the absence of an obvious way to proceed, I gave up :-) |
Actually, this is *exactly* how I ended up thinking about this feature. I was using a separate dict to track the index at which objects are inserted in a heap, using the index to make updates to heap directly, and fixing the heap by calling heapify() every time which was slightly costly. Maybe I chose the wrong data structure for the problem, but constant time getMin() operation was crucial for me. And I didn't really care if inserts (or updates) were costlier. But I completely agree that it's a niche use case and I understand if we don't want to support this :) |
And yes, both of these methods do take index as the argument as shown in my patch file. I should've probably specified that. The signatures are: heapfix(heap, pos)
heapremove(heap, pos) |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: