我知道可以在 O(log n) 中实现减少键功能,但我不知道如何?
6 回答
为了有效地实现“减少键”,您需要访问“减少此元素并与子元素交换此元素,直到堆条件恢复”的功能。在heapq.py中,这被称为_siftdown
(_siftup
对于增量也是类似的)。所以好消息是这些函数就在那里......坏消息是它们的名称以下划线开头,表明它们被认为是“内部实现细节”,不应由应用程序代码直接访问(下一个版本的标准库可能会使用这种“内部结构”改变事物并破坏代码)。
由您决定是否要忽略警告前导_
-,使用 O(N)heapify
而不是 O(log N) 筛选,或者重新实现 heapq 的部分或全部功能以使筛选原语“公开为界面”。由于 heapq 的数据结构已记录并公开(只是一个列表),我认为最好的选择可能是部分重新实现——本质上,将筛选函数从 heapq.py 复制到您的应用程序代码中。
Decrease-key 是很多算法(Dijkstra's Algorithm, A*, OPTICS)的必备操作,我想知道为什么 Python 的内置优先级队列不支持它。
不幸的是,我无法下载 math4tots 的软件包。
但是,我能够找到Daniel Stutzbach 的这个实现。使用 Python 3.5 非常适合我。
hd = heapdict()
hd[obj1] = priority
hd[obj1] = lower_priority
# ...
obj = hd.pop()
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.
虽然它很新,所以可能充满了错误。
想象一下,您正在使用堆作为优先级队列,其中有一堆由字符串表示的任务,每个任务都有一个键。具体而言,请查看:task_list = [[7,"do laundry"], [3, "clean room"], [6, "call parents"]]
其中的每个任务task_list
都是具有优先级和描述的列表。如果你运行heapq.heapify(task_list)
,你会让你的数组保持堆不变。但是,如果您想将“洗衣服”的优先级更改为 1,如果没有对堆进行线性扫描,您将无法知道“洗衣服”在堆中的位置(因此不能在对数时间内执行 reduce_key) . 注意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。
拥有该decrease_key
功能可能是不必要的(尽管拥有它很好)。
无论如何,您都可以将其推(priority, item)
入优先级队列,并使用 aset
检查您是否已看到它。例如:
pq = [] # heapq is a min heap
seen = set()
heappush(pq, (2, "item1"))
heappush(pq, (3, "item2"))
heappush(pq, (1, "item3"))
heappush(pq, (4, "item4"))
heappush(pq, (2, "item2"))
while pq:
p, item = heappop(pq)
if item not in seen:
seen.add(item)
print(item, p)
else:
print(item, "is already handled with a higher priority!")
输出是:
item3 1
item1 2
item2 2
item2 is already handled with a higher priority!
item4 4
C++ 和 Java 标准库优先级队列也缺少此功能。标准的解决方法是推送一个新的键值对,并隐式或显式地将原始键值对标记为无效。请参阅如何更新堆内的元素?(优先队列)