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

Question

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

Answer 1

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

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