如何在Python的heapq中实现降低关键字功能？

Question

我知道可以用 O(log n) 的时间复杂度实现 decrease-key 功能，但是我不知道怎么做？

- zerodx

---

请参阅 https://dev59.com/OWox5IYBdhLWcg3wWzJ7 以及我的回答，解释为什么不需要使用 decrease-key 函数。 - qwr

Answer 1

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

由您决定是否要忽略警告前缀_，使用O（N） heapify 而不是O（log N）筛选，或重新实现一些或所有heapq的功能，使筛选原语“公开为接口的一部分”。由于heapq的数据结构已记录并公开（只是一个列表），我认为最好的选择可能是部分重新实现 - 将sifting功能从heapq.py复制到应用程序代码中。

- Alex Martelli

---

看起来 heapq.py 的链接已经过期了。为了方便起见，这里提供另一个 Python 实现的链接：http://hg.python.org/cpython/file/2.7/Lib/heapq.py - Jordan

你的意思是“将此元素与其_parent_交换，直到堆条件恢复”吗？（我假设如果有元素[2, 3, 5]，那么2将是父元素，3和5将是其两个子元素） - tscizzle

需要注意的是，即使您可以实现“减少键”或更通用的“更新键”，该功能也假定您有一种跟踪堆上索引的方法，以便您可以确定要操作的项目（否则您可能必须在线性时间内搜索它）。第一个明显的解决方案是使用键到索引哈希映射来增强堆结构。从那时起，堆更改操作（例如_siftup和_siftdown）应触发地图的更新。 - Michael Ekoka

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()

- Guy s

---

这不是必须的，因为有解决方法。https://dev59.com/YVYN5IYBdhLWcg3wuaNx?noredirect=1&lq=1 - qwr

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. 

它相当新，可能会有很多漏洞。

- math4tots

---

可以承认的是，文档中提到的解决方案相当繁琐。它建议在更改堆中的值时，保留旧值并在其上设置某个标记以指示其无效性，同时插入新元素。当您频繁更改值（没有任何中间弹出）时，您的堆只会不断增长，包含大量“死”垃圾。然后有“无效”标记本身的开销：当仅存储整数时，这些“无效”标记是相当大的开销。这不是一个很好的解决方案。 - bluenote10

Answer 4

假设您正在使用堆作为优先队列，其中有一堆由字符串表示的任务，并且每个任务都有一个键。为了具体化，看一下：task_list = [[7,"do laundry"], [3, "clean room"], [6, "call parents"]]，其中task_list中的每个任务都是一个具有优先级和描述的列表。如果运行heapq.heapify(task_list)，则可以使数组维护堆不变量。然而，如果您想将“do laundry”的优先级更改为1，则无法在不通过堆进行线性扫描的情况下知道“do laundry”在堆中的位置（因此无法在对数时间内进行降低关键字操作）。请注意，decrease_key(heap, i, new_key)要求您知道要在堆中更改值的索引。

即使您保留对每个子列表的引用并实际更改键，仍无法在对数时间内完成此操作。因为列表只是对一堆可变对象的引用，所以您可以尝试做一些事情，比如记住任务的原始顺序：（在这种情况下，“do laundry”是您原始task_list中的第0个任务）：

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。

- dr jimbob

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

- kigawas

Answer 6

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

请参见如何更新堆内元素？（优先队列）和Dijkstra算法为什么要使用减少键操作？（结论是，理论上和实际上没有减少键操作不会对运行时间产生显著影响；特别是请参见论文https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf）

- qwr

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())

- Swapnil Masurekar