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_heapheap_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 回答