[issue31186] Support heapfix() and heapremove() APIs in heapq module

[Rajath Agasthya]

Rajath Agasthya added the comment:

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)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue31186] Support heapfix() and heapremove() APIs in heapq module

[Rajath Agasthya]

Rajath Agasthya added the comment:

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

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 :)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue31186] Support heapfix() and heapremove() APIs in heapq module

[Tim Peters]

Tim Peters added the comment:

@Rajath, I suspect Raymond may have been bamboozled because your suggested 
`heapfix()` and `heapremove()` didn't appear to take any arguments.  If the 
index is a required argument, then these are O(log N) operations.

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 :-)

--
nosy: +tim.peters

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue31186] Support heapfix() and heapremove() APIs in heapq module

[Rajath Agasthya]

Rajath Agasthya added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue31186] Support heapfix() and heapremove() APIs in heapq module

[Raymond Hettinger]

Raymond Hettinger added the comment:

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

--
resolution:  -> rejected
stage:  -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue31186] Support heapfix() and heapremove() APIs in heapq module

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
assignee:  -> rhettinger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue31186] Support heapfix() and heapremove() APIs in heapq module

[Rajath Agasthya]

New submission from Rajath Agasthya:

I'd like to suggest a couple of utility methods for the heapq module which I 
think are useful:

1. heapfix() - Re-establishes heap invariant after item at 'any index' in the 
heap changes its value.

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.

2. heapremove() - Removes an item at 'any index' from the heap and maintains 
heap invariant.

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!

--
components: Library (Lib)
files: heapq_fix_remove.patch
keywords: patch
messages: 300190
nosy: rajathagasthya, rhettinger, stutzbach
priority: normal
severity: normal
status: open
title: Support heapfix() and heapremove() APIs in heapq module
type: enhancement
versions: Python 3.7
Added file: http://bugs.python.org/file47079/heapq_fix_remove.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com