如何在 Python 的 heapq 中实现减键功能？

How can I implement decrease-key functionality in Python's heapq?

提问by Alex Martelli

I know it is possible to realize decrease-key functionality in O(log n) but I don't know how?

我知道可以在 O(log n) 中实现减键功能，但我不知道如何实现？

回答by Alex Martelli

To implement "decrease-key" effectively, you'd need to access the functionality "decrement this element AND swap this element with a child until heap condition is restore". In heapq.py, that's called _siftdown(and similarly _siftupfor INcrementing). So the good news is that the functions are there... the bad news is that their names start with an underscore, indicating they're considered "internal implementation details" and should not be accessed directly by application code (the next release of the standard library might change things around and break code using such "internals").

要有效地实现“减少键”，您需要访问“减少此元素并将此元素与子元素交换直到堆条件恢复”的功能。在heapq.py 中，这被称为_siftdown（_siftup对于 INcrementing也是如此）。所以好消息是函数在那里......坏消息是它们的名称以下划线开头，表明它们被视为“内部实现细节”，不应由应用程序代码直接访问（下一个版本的标准库可能会使用这种“内部结构”来改变事物并破坏代码）。

It's up to you to decide whether you want to ignore the warning leading-_, use O(N) heapifyinstead of O(log N) sifting, or reimplement some or all of heapq's functionality to make the sifting primitives "exposed as public parts of the interface". Since heapq's data structure is documented and public (just a list), I think the best choice is probably a partial-reimplementation -- copy the sifting functions from heapq.py into your application code, essentially.

由您决定是否要忽略前​​导警告_，使用 O(N)heapify而不是 O(log N) 筛选，还是重新实现部分或全部 heapq 的功能以使筛选原语“作为公共部分公开”界面”。由于 heapq 的数据结构已记录并公开（只是一个列表），我认为最好的选择可能是部分重新实现——本质上是将 heapq.py 中的筛选函数复制到您的应用程序代码中。

回答by Guy s

Decrease-key is a must-have operation for many algorithms (Dijkstra's Algorithm, A*, OPTICS), i wonder why Python's built-in priority queue does not support it.

Decrease-key 是很多算法（Dijkstra's Algorithm, A*, OPTICS）的必备操作，我想知道为什么Python内置的优先级队列不支持它。

Unfortunately, i wasn't able to download math4tots's package.

不幸的是，我无法下载 math4tots 的软件包。

But, i was able to find thisimplementation by Daniel Stutzbach. Worked perfectly for me with Python 3.5.

但是，我能够找到Daniel Stutzbach 的这个实现。使用 Python 3.5 非常适合我。

hd = heapdict()
hd[obj1] = priority
hd[obj1] = lower_priority
# ...
obj = hd.pop()

回答by dr jimbob

Imagine you are using a heap as a priority queue, where you have a bunch of tasks represented by strings and each task has a key. For concreteness, look at: task_list = [[7,"do laundry"], [3, "clean room"], [6, "call parents"]]where each task in task_listis a list with a priority and description. If you run heapq.heapify(task_list), you get your array to maintain the heap invariant. However, if you want to change the priority of "do laundry" to 1, you have no way of knowing where "do laundry" is in the heap without a linear scan through the heap (hence can't do decrease_key in logarithmic time). Note decrease_key(heap, i, new_key)requires you to know the index of the value to change in the heap.

假设您使用堆作为优先级队列，其中有一堆由字符串表示的任务，每个任务都有一个键。具体来说，请看：task_list = [[7,"do laundry"], [3, "clean room"], [6, "call parents"]]其中的每个任务task_list都是一个带有优先级和描述的列表。如果你运行heapq.heapify(task_list)，你会让你的数组保持堆不变。但是，如果您想将“洗衣”的优先级更改为 1，如果不通过堆进行线性扫描，您将无法知道“洗衣”在堆中的哪个位置（因此无法在对数时间内执行减少键） . 注意decrease_key(heap, i, new_key)要求您知道要在堆中更改的值的索引。

Even if you maintain a reference to each sublist and actually change the key, you still can't do it in log time. Since a list is just a reference to a bunch of mutable objects, you could try doing something like remember the original order of the task: (in this case that "do laundry" was the 0th task in your original task_list):

即使你维护了对每个子列表的引用并实际更改了密钥，你仍然无法在日志时间这样做。由于列表只是对一堆可变对象的引用，您可以尝试做一些事情，例如记住任务的原始顺序：（在这种情况下，“洗衣服”是原始任务中的第 0 个任务task_list）：

task_list = [[7, "do laundry"], [3, "clean room"], [6, "call parents"]]
task_list_heap = task_list[:] # make a non-deep copy
heapq.heapify(task_list_heap)
# at this point:
# task_list = [[7, 'do laundry'], [3, 'clean room'], [6, 'call parents']]
# task_list_heap = [3, 'clean room'], [7, 'do laundry'], [6, 'call parents']]
# Change key of first item of task_list (which was "do laundry") from 7 to 1.
task_list[0][0] = 1
# Now:
# task_list = [[1, 'do laundry'], [3, 'clean room'], [6, 'call parents']]
# task_list_heap = [3, 'clean room'], [1, 'do laundry'], [6, 'call parents']]
# task_list_heap violates heap invariant at the moment

However, you now need to call heapq._siftdown(task_list_heap, 1)to maintain the heap invariant in log time (heapq.heapifyis linear time), but unfortunately we don't know the index of "do laundry" in task_list_heap(the heap_indexin this case is 1).

但是，您现在需要调用heapq._siftdown(task_list_heap, 1)以在日志时间（heapq.heapify是线性时间）中保持堆不变，但不幸的是，我们不知道“洗衣”中的索引task_list_heap（heap_index在这种情况下为 1）。

So we need to implement our heap keeps track of the heap_indexof each object; e.g., have an list(for the heap) and a dictmapping each object to its index in the heap/list (that gets updated as the heap positions get swapped adding a constant factor to each swap). You could read through heapq.pyand implement yourself as the procedure is straightforward; however, others have implement this sort of HeapDictalready.

所以我们需要实现我们的堆跟踪heap_index每个对象；例如，有一个list（对于堆）和一个dict映射每个对象到它在堆/列表中的索引（随着堆位置交换而更新，为每个交换添加一个常数因子）。您可以通读heapq.py并自行实现，因为该过程很简单；然而，其他人已经实现了这种HeapDict。

回答by math4tots

The heapq documentationhas an entry on exactly how to do this.

该heapq文档对究竟是如何做到这一点的条目。

However, I have written a heappackage that does exactly this (it is a wrapper around heapq). So if you have pipor easy_installyou could do something like

但是，我已经编写了一个heap完全执行此操作的包（它是围绕 的包装器heapq）。所以如果你有pip或者easy_install你可以做类似的事情

pip install heap

Then in your code write

然后在你的代码中写

from heap.heap import heap

h = heap()

h['hello'] = 4 # Insert item with priority 4.

h['hello'] = 2 # Update priority/decrease-key has same syntax as insert. 

It ispretty new though, so might be full of bugs.

这是很新的，所以可能是完全错误的。