While reading heapq
source's code, I noticed as @math4tots did that it was importing a C implementation. So I ran the following to prove whether it is using the python source (which would call methods from list
that are overloadable), or it's using the C implementation that uses compiled methods for lists:
>>> 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}
it does not printout a single string… which means it does not use the python sources we were looking at, but definitely the compiled version.
So your code is unlikely to work as is…
Reading the C source code of the heapq module
proves us right: the _siftup
function is using PyList_SET_ITEM()
to get values from the list overriding any attempt to overload the method.
Though, all hope is not lost, reading the C source code further on, made me discover that actually the C module does not export the _sitf*
functions implementing the heapq algorithms. So I've looked at the following, as a double check:
>>> heapq.heapify
<built-in function heapify>
>>> heapq._siftup
<function _siftup at 0x10b36ab00>
Which proved me right!
So, you can always reimplement the heapify()
and heappush()
functions which are about a couple of lines long, by using the _siftup()
and _siftdown()
functions from heapq module that are not shadowed by the C code.
so here would be a take at reimplementing it:
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)
results:
>>> 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]
>>>
my guess is that you wouldn't want to keep that heapify()
method, but instead make it as part of the constructor, and think through a nicer interface for your own Heap Queue class. I've only did it as proof of concept for that idea.
HTH