拦截堆

Question

我想使用Python的heapq模块。但是，我需要跟踪每个值设置的索引。

所以我写了

class heap(list):       
    def __init__(self,xs):
        super(heap,self).__init__(xs)
        self._index_table = {x:i for i,x in enumerate(self)}

    def __setitem__(self,i,v):
        print(i,v)
        super(heap,self).__setitem__(i,v)
        self._index_table[v] = i

    def append(self,x):
        super(heap,self).append(x)
        self._index_table[x] = len(self)-1

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

h = heap([4,3,2,1])
heapify(h)
heappush(h,12)
print(h)
print(h._index_table)

这个指纹

[1, 3, 2, 4, 12]
{1: 3, 2: 2, 3: 1, 4: 0}

heapify和heappush修改了我列表中的条目，避免了我试图捕获所有赋值的尝试。

为什么会发生这种情况？有办法绕道吗？是否还有一种方法可以使用heapq模块并仍然跟踪每个值对应的索引？

编辑：

看起来我的代码中有一个heapify(h)行，我在最初的文章中没有。修好了这个。

Answer 1

在阅读heapq源代码时，我注意到@math4tots正在导入一个C实现。因此，我运行了下面的代码来证明它是在使用python源代码(它将从list调用可重载的方法)，还是使用C实现对列表使用编译的方法：

>>> class heap(list):        
...     def __init__(self,xs):
...         super(heap,self).__init__(xs)
...         self._index_table = {x:i for i,x in enumerate(self)}
...     
...     def __setitem__(self,i,v):
...         print("SETITEM")
...         print(i,v)
...         super(heap,self).__setitem__(i,v)
...         self._index_table[v] = i
...     
...     def append(self,x):
...         print("APPEND")
...         super(heap,self).append(x)
...         self._index_table[x] = len(self)-1
... 
>>> 
>>> 
>>> h = heap([4,3,2,1])
>>> heapify(h)
>>> h
[1, 3, 2, 4]
>>> h._index_table
{1: 3, 2: 2, 3: 1, 4: 0}
>>> heappush(h,42)
>>> h
[1, 3, 2, 4, 42]
>>> h._index_table
{1: 3, 2: 2, 3: 1, 4: 0}

它不输出单个字符串…。这意味着它没有使用我们正在查看的python源代码，而是使用了编译后的版本。

因此，您的代码不太可能像…那样工作。

阅读heapq module的C源代码证明我们是正确的：_siftup函数使用PyList_SET_ITEM()从列表中获取值，覆盖任何重载该方法的尝试。

虽然，所有的希望都没有失去，继续阅读C源代码，让我发现其实C模块不出口的_sitf*函数实现了heapq算法。因此，我看了以下几点，作为一次复核：

>>> heapq.heapify
<built-in function heapify>
>>> heapq._siftup
<function _siftup at 0x10b36ab00>

这证明我是对的！

因此，您始终可以重新实现heapify()和heappush()函数，它们大约有几行长，方法是使用未被C代码遮蔽的heapq模块中的_siftup()和_siftdown()函数。

因此，这里将是重新实现它的一个步骤：

import heapq

class HeapQueue(list):
    def __init__(self,xs):
        super(HeapQueue,self).__init__(xs)
        self._index_table = {x:i for i,x in enumerate(self)}
    def __setitem__(self,i,v):
        super(HeapQueue,self).__setitem__(i,v)
        self._index_table[v] = i
    def append(self,x):
        super(HeapQueue,self).append(x)
        self._index_table[x] = len(self)-1
    def push(self, x):
        self.append(x)
        heapq._siftdown(self, 0, len(self)-1)
    def heapify(self):
        n = len(self)
        for i in reversed(range(n//2)):
            heapq._siftup(self, i)

结果：

>>> h = HeapQueue([4,3,2,1])
>>> print(h._index_table)
{1: 3, 2: 2, 3: 1, 4: 0}
>>> h.heapify()
>>> print(h)
[1, 3, 2, 4]
>>> print(h._index_table)
{1: 0, 2: 2, 3: 1, 4: 3}
>>> h.push(42)
>>> print(h._index_table)
{1: 0, 2: 2, 3: 1, 4: 3, 42: 4}
>>> print(h)
[1, 3, 2, 4, 42]
>>> 

我的猜测是，您不希望保留该heapify()方法，而是将其作为构造函数的一部分，并为您自己的堆队列类考虑一个更好的接口。我这么做只是为了证明这个想法的概念。

HTH