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

Question

我知道可以在O(log n)的时间内实现减少键值的功能，但我不知道具体怎么做。

Answer 1

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. 

不过这个包还挺新的，所以可能会有很多bug。

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

要有效地实现“减小键值”的功能，你需要能够访问一个功能，这个功能可以“减少这个元素的值，并且把这个元素和它的子节点交换，直到堆的条件恢复”。在heapq.py文件中，这个功能叫做_siftdown（而增加键值的功能叫_siftup）。好消息是这些函数是存在的……坏消息是它们的名字前面有个下划线，这表示它们被认为是“内部实现细节”，不应该被应用程序的代码直接访问（标准库的下一个版本可能会改变这些内容，从而导致使用这些“内部”功能的代码出错）。

你可以自己决定是否要忽略这个前缀警告，选择用O(N)的heapify替代O(log N)的筛选，或者重新实现heapq的一部分或全部功能，使得筛选的基本功能“作为接口的公共部分暴露出来”。因为heapq的数据结构是公开的（其实就是一个列表），我认为最好的选择可能是部分重新实现——也就是说，把heapq.py中的筛选函数复制到你的应用代码中。