采用树形结构实现优先队列的技术称为堆
优先队列，就是值最小的排在队头，值最大的排在队尾，还有插入新元素的问题，插入的算法复杂度O（n）,如果采用基于堆的优先队列，算法复杂度O（lgn），插入堆采用插入元素向上筛选，就是从底部到顶部一级一级跳跃，直到上一个root比元素值小或者本身到了root，删除元素向下筛选
class PrioQueue():
def __init__(self,elist=[]):
self._elems = list(elist)
if elist:
self.buildheap()
def is_empty(self):
return not self._elems
def peek(self):
if self.is_empty():
raise PrioQueueError("in peek")
return self._elems[0]
def enqueue(self,e):
self._elems.append(None) #add a dummy element
self.siftup(e,len(self._elems) -1 )
def seftup(self , e, last):
elems,i,j=self._elems,last,(last-1)//2
while i>0 and e < elems[j]:
elems[i] = elems[j]
i,d=j,(j-1)//2
elems[i] = e
def dequeue(self):
if self.is_empty():
raise PrioQueueError("in dequeue")
elems = self._elems
e0 = elems[0]
e = elems.pop()
if len(elems) > 0:
self.siftdowm(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+1] < elems[j]:
j +=1
if e < elems[j]:
break
elems[i] = elems[j]
i,j = j, 2*j+1
elems[i] = e
def buildheap(self):
end = len(self._elems)
for i in range(end/2,-1,-1):
self.siftdown(self._elems[i],i,end)
def printnum(self):
print self._elems
堆排序：如果一个连续表里存储的数据是一个小顶堆，按优先队列的方式反复弹出堆顶元素，能够得到一个递增序列。基于这个技术可以完成堆排序，下面是堆排序算法，siftdown是向下弹出堆顶元素，siftup是向上插入
def heap_sort(elems):
def siftdown(elems, e, begin, end):
i,j = begin, begin*2+1
while j< end:
if j+1 < end and elems[j+1] <elems[j]:
j +=1
if e<elems[j]:
break
elems[i] = elems[j]
i,j = j, 2*j+1
elems[i] = e
end = len(elems)
for i in range(end//2, -1, -1):
siftdown(elems, elems[i],i, end)
for i in range((end -1),0,-1):
e = elems[i]
elems[i] = elems[0]
siftdown(elems,e,0,i)
