如何在 Python 的 heapq 中实现减少键功能？

Question

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

Answer 1

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

由您决定是否要忽略前​​导-_ 警告，使用 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

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. 

It is 不过，它是相当新的，因此可能充满错误。

Answer 4

想象一下，您正在使用堆作为优先级队列，其中有一堆由字符串表示的任务，每个任务都有一个键。具体而言，请查看：task_list = [[7,"洗衣服"], [3,"洁净室"], [6,"打电话给父母"]]，其中 中的每个任务task_list 是一个带有优先级和描述的列表。如果运行 heapq.heapify(task_list)，您的数组将保持堆不变量。但是，如果您想将“do洗衣”的优先级更改为1，则在不线性扫描堆的情况下，您无法知道“do洗衣”在堆中的位置（因此无法在对数时间内执行decrease_key） 。注意 decrease_key(heap, i, new_key) 要求您知道堆中要更改的值的索引。

即使您维护对每个子列表的引用并实际更改键，您仍然无法在日志时间内完成此操作。由于列表只是对一堆可变对象的引用，因此您可以尝试执行以下操作：记住任务的原始顺序：（在本例中，“洗衣服”是原始 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 5

可能没有必要使用 decrease_key 函数（尽管拥有它很好）。

无论如何，您都可以将您的 (priority, item) 推入优先级队列，并使用 set 来检查您是否已经看到它。例如：

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

Answer 6

C++ 和 Java 标准库优先级队列也缺少此功能。标准解决方法是推送新的键值对，并隐式或显式地将原始键值对标记为无效。

请参阅如何更新其中的元素一堆？ （优先级队列）和为什么Dijkstra算法使用decrease-key？ （结论是，没有减少键不会在理论上和实践中显着影响运行时；特别是参见论文 https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf)

Answer 7

使用具有唯一键的最小堆的优先级队列简单实现。如果优先级队列中已存在键，则此实现会在 push() 操作期间更新键的优先级。

import heapq

class HeapPQ:
    """
    Only hashable key type is supported
    """

    def __init__(self):
        self.pq = []
        self.pq_set = set()
    
    def push(self, priority, key):
        if key not in self.pq_set:
            heapq.heappush(self.pq, (priority, key))
            self.pq_set.add(key)
        else:
            index = list(map(lambda x:x[1], self.pq)).index(key)
            self.pq[index] = (priority, key)
            heapq.heapify(self.pq)
    
    def pop(self):
        priority, key = heapq.heappop(self.pq)
        self.pq_set.remove(key)
        return priority, key
    
    def empty(self) -> bool:
        return len(self.pq) == 0

用法示例：

pq = HeapPQ()

pq.push(5, "A")
pq.push(3, "B")
pq.push(1, "A")

while not pq.empty():
    print(pq.pop())