如何在Python的heapq中实现reduce-key功能？

Question

我知道有可能在O(log n)中实现减少键功能,但我不知道怎么做？

Answer 1

要有效地实现"减少键",您需要访问"减少此元素并与子项交换​​此元素直到堆条件恢复"的功能.在heapq.py中,被调用_siftdown(并且类似于_siftupINcrementing).所以好消息是功能在那里......坏消息是他们的名字以下划线开头,表明他们被认为是"内部实现细节",不应该直接通过应用程序代码访问(下一个版本的标准库可能会改变现状并使用这样的"内部"来破坏代码.

由您来决定是否要忽略警告前导_,使用O(N)heapify而不是O(log N)筛选,或重新实现heapq的部分或全部功能,以使筛选原语"作为公共部分暴露"接口".由于heapq的数据结构是文档化的并且是公共的(只是一个列表),我认为最好的选择可能是部分重新实现 - 将heapq.py中的筛选函数复制到应用程序代码中.

Answer 2

Decrease-key是许多算法必不可少的操作(Dijkstra算法,A*,OPTICS),我想知道为什么Python的内置优先级队列不支持它.

不幸的是,我无法下载math4tots的软件包.

但是,我能够找到Daniel Stutzbach的这个实现.使用Python 3.5完美地为我工作.

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

Answer 3

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

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

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

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

Answer 4

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

但是,我编写了一个heap完全符合它的包(它是一个包装器heapq).所以,如果你有pip或easy_install你可以做类似的事情

pip install heap

然后在你的代码中写

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. 

这是很新的,所以可能是完全错误的.