43

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

4

6 回答 6

43

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

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

于 2009-09-23T14:41:15.073 回答
14

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()
于 2016-05-03T15:12:58.850 回答
7

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.

虽然它很新，所以可能充满了错误。

于 2014-05-17T03:24:32.560 回答
6

想象一下，您正在使用堆作为优先级队列，其中有一堆由字符串表示的任务，每个任务都有一个键。具体而言，请查看：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。

于 2012-12-10T15:47:50.463 回答
2

拥有该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
于 2021-02-03T09:46:14.233 回答
1

C++ 和 Java 标准库优先级队列也缺少此功能。标准的解决方法是推送一个新的键值对，并隐式或显式地将原始键值对标记为无效。请参阅如何更新堆内的元素？（优先队列）

于 2021-10-07T05:13:01.463 回答