相关疑难解决方法(0)

如何避免在 heapq 中使用 _siftup 或 _siftdown

我不知道如何在不使用_siftupor 的情况下有效地解决以下问题_siftdown

当一个元素无序时,如何恢复堆不变式?

换句话说,更新old_valueheapnew_value,并保持heap工作。您可以假设old_value堆中只有一个。功能定义如下:

def update_value_in_heap(heap, old_value, new_value):
Run Code Online (Sandbox Code Playgroud)

这是我的真实场景,有兴趣的可以看看。

  • 你可以想象它是一个小型的自动完成系统。我需要统计单词出现的频率,并保持前k个max-count单词,随时准备输出。所以我heap在这里使用。当一个字数++时,如果它在堆中,我需要更新它。

  • 所有的词和计数都存储在 trie-tree 的叶子中,heaps
    存储在 trie-tree 的中间节点中。如果你关心
    堆外这个词,别担心,我可以从trie-tree的叶子节点中得到它。

  • 当用户输入一个单词时,它将首先从堆中读取然后更新
    它。为了获得更好的性能,我们可以考虑通过批量更新来降低更新频率。

那么当一个特定的字数增加时,如何更新堆呢?

这是 _siftup 或 _siftdown 版本的简单示例(不是我的场景):

>>> from heapq import _siftup, _siftdown, heapify, heappop

>>> data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
>>> heapify(data)
>>> old, new = 8, 22              # increase the 8 to 22
>>> i = data.index(old) …
Run Code Online (Sandbox Code Playgroud)

python heap

5
推荐指数
2
解决办法
1288
查看次数

标签 统计

heap ×1

python ×1