1 #!/usr/bin/env python 2 # -*- coding:utf-8 -*- 3 4 ''' 5 Author: Minion-Xu 6 ''' 7 8 #异常类 9 class HeapPriQueueError(ValueError):10 pass11 12 class Heap_Pri_Queue(object):13 def __init__(self, elems = []):14 self._elems = list(elems)15 if self._elems:16 self.buildheap()17 18 #判断是否为空19 def is_empty(self):20 return self._elems is []21 22 #查看堆顶元素，即优先级最低元素23 def peek(self):24 if self.is_empty():25 raise HeapPriQueueError("in pop")26 return self._elems[0]27 28 #将新的优先级加入队列 O(logn)29 def enqueue(self, e):30 #在队列末尾创建一个空元素31 self._elems.append(None)32 self.siftup(e, len(self._elems) - 1)33 34 #新的优先级默认放在末尾，因此失去堆序，进行siftup构建堆序35 #将e位移到真确的位置36 def siftup(self, e, last):37 elems, i, j = self._elems, last, (last-1)//2 #j为i的父节点38 while i>0 and e < elems[j]:39 elems[i] = elems[j]40 i, j = j, (j-1)//241 elems[i] = e42 43 #堆顶值最小优先级最高的出队,确保弹出元素后任然维持堆序44 #将最后的元素放在堆顶，然后进行siftdown45 # O(logn)46 def dequeue(self):47 if self.is_empty():48 raise HeapPriQueueError("in pop")49 elems = self._elems50 e0 = elems[0]51 e = elems.pop()52 if len(elems)>0:53 self.siftdown(e, 0, len(elems))54 return e055 56 def siftdown(self, e, begin, end):57 elems, i, j = self._elems, begin, begin*2 + 158 while j < end:59 if j+1 < end and elems[j] > elems[j+1]:60 j += 161 if e < elems[j]:62 break63 elems[i] = elems[j]64 i, j = j, j*2+165 elems[i] = e66 67 #构建堆序 O(n)68 def buildheap(self):69 end = len(self._elems)70 for i in range(end//2, -1, -1):71 self.siftdown(self._elems[i], i, end)72 73 74 if __name__=="__main__":75 l = Heap_Pri_Queue([5,6,1,2,4,8,9,0,3,7])76 print(l._elems)77 #[0, 2, 1, 3, 4, 8, 9, 6, 5, 7]78 l.dequeue()79 print(l._elems)80 #[1, 2, 7, 3, 4, 8, 9, 6, 5]81 print(l.is_empty())82 l.enqueue(0)83 print(l._elems)84 print(l.peek())
插入元素：末尾插入， 向上筛选（siftup）
弹出元素：堆顶弹出， 末尾元素充当堆顶， 向下筛选（siftdown）