上QQ阅读APP看书，第一时间看更新
4.3.5 实践演练——基于堆实现的优先队列
下面的实例文件dui.py演示了基于堆实现优先队列的过程。
源码路径：daima\第4章\dui.py
class Heap_Pri_Queue(object):
def __init__(self, elems = []):
self._elems = list(elems)
if self._elems:
self.buildheap()
#判断是否为空
def is_empty(self):
return self._elems is []
#查看堆顶元素，即优先级最低的元素
def peek(self):
if self.is_empty():
raise HeapPriQueueError("in pop")
return self._elems[0]
#将新的优先级加入队列O(log n)
def enqueue(self, e):
#在队列末尾创建一个空元素
self._elems.append(None)
self.siftup(e, len(self._elems) - 1)
#新的优先级默认放在末尾，因此失去堆序，进行siftup，构建堆序
#将e位移到正确的位置
def siftup(self, e, last):
elems, i, j = self._elems, last, (last-1)//2 #j为i的父节点
while i>0 and e < elems[j]:
elems[i] = elems[j]
i, j = j, (j-1)//2
elems[i] = e
#堆顶值最小、优先级最高的出队，确保弹出元素后仍然维持堆序
#将最后的元素放在堆顶，然后进行siftdown
# O(log2n)
def dequeue(self):
if self.is_empty():
raise HeapPriQueueError("in pop")
elems = self._elems
e0 = elems[0]
e = elems.pop()
if len(elems)>0:
self.siftdown(e, 0, len(elems))
return e0
def siftdown(self, e, begin, end):
elems, i, j = self._elems, begin, begin*2 + 1
while j < end:
if j+1 < end and elems[j] > elems[j+1]:
j += 1
if e < elems[j]:
break
elems[i] = elems[j]
i, j = j, j*2+1
elems[i] = e
#构建堆序O(n)
def buildheap(self):
end = len(self._elems)
for i in range(end//2, -1, -1):
self.siftdown(self._elems[i], i, end)
if __name__=="__main__":
l = Heap_Pri_Queue([5,6,1,2,4,8,9,0,3,7])
print(l._elems)
#[0, 2, 1, 3, 4, 8, 9, 6, 5, 7]
l.dequeue()
print(l._elems)
#[1, 2, 7, 3, 4, 8, 9, 6, 5]
print(l.is_empty())
l.enqueue(0)
print(l._elems)
print(l.peek())
执行后会输出：
[0, 2, 1, 3, 4, 8, 9, 6, 5, 7] [1, 2, 7, 3, 4, 8, 9, 6, 5] False [0, 1, 7, 3, 2, 8, 9, 6, 5, 4] 0