如何在Python的heapq中实现减键功能? [英] How can I implement decrease-key functionality in Python's heapq?

问题描述

我知道可以在O(log n)中实现减键功能，但是我不知道怎么办?

I know it is possible to realize decrease-key functionality in O(log n) but I don't know how?

推荐答案

要有效实现"decrease-key"，您需要访问减少此元素并将其与子元素交换，直到恢复堆条件"的功能. ".在 heapq.py 中，这称为_siftdown(和类似_siftup进行递增).因此，好消息是这些函数在那里...坏消息是它们的名称以下划线开头，表明它们被视为内部实现细节"，不应由应用程序代码直接访问(该版本的下一个版本)标准库可能会使用这种内部函数"改变周围的事物并破坏代码.)

To implement "decrease-key" effectively, you'd need to access the functionality "decrement this element AND swap this element with a child until heap condition is restore". In heapq.py, that's called _siftdown (and similarly _siftup for INcrementing). So the good news is that the functions are there... the bad news is that their names start with an underscore, indicating they're considered "internal implementation details" and should not be accessed directly by application code (the next release of the standard library might change things around and break code using such "internals").

由您决定是否要忽略警告行首-_，使用O(N)heapify而不是O(log N)筛选，还是重新实现heapq的部分或全部功能以使筛选基元作为接口的公共部分公开".由于heapq的数据结构是公开的(只是列表)，因此，我认为最好的选择可能是部分重新实现-本质上将筛选功能从heapq.py复制到您的应用程序代码中.

It's up to you to decide whether you want to ignore the warning leading-_, use O(N) heapify instead of O(log N) sifting, or reimplement some or all of heapq's functionality to make the sifting primitives "exposed as public parts of the interface". Since heapq's data structure is documented and public (just a list), I think the best choice is probably a partial-reimplementation -- copy the sifting functions from heapq.py into your application code, essentially.

这篇关于如何在Python的heapq中实现减键功能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！