優先隊列(PRiority queue)是允許至少兩種操作的數據結構:Insert及DeleteMin(刪除最小者)。相當于隊列中的Enqueue、Dequeue操作。
優先隊列可以用鏈表、二叉查找樹、二叉堆等實現。
1. 結構性質
堆(heap)是一棵完全被填滿的二叉樹，有可能的例外是在底層，底層上的元素從左向右填入。這樣的樹稱之為完全二叉樹。
一棵高為h的完全二叉樹有2h到2h+1-1個節點。完全二叉樹的高為logN。
完全二叉樹可以用數組來表示，如果從0開始，對于數組中任意i位置的元素，其左兒子在2i+1位置上，右兒子在2i+2位置上，父節點在floor((i-1)/2)位置上。
2.堆序性質
最小堆：對于堆中的每一個節點，其子節點的關鍵字都大于其的關鍵字，根節點處為最小值。
最大堆：對于堆中的每一個節點，其子節點的關鍵字都小于其的關鍵字，根節點處為最大值。
3.基本的堆操作
Insert：
將要插入的元素X放入到堆末尾，如果不破壞堆的結構，操作完成，否則將X上濾。
如果欲插入的元素一直上濾到根處，那么插入的時間高達O(logN)。平均看來，這種上濾要終止的早。基本上執行一次插入平均需要2.607次比較。
DeleteMin：
對于最小堆，刪除根節點，將堆末尾的節點放到根部，然后執行下濾操作。操作的平均操作時間為O(logN)。
最小堆的其它操作：
DecreaseKey(降低關鍵字的值)：執行上濾操作。
IncreaseKey(增加關鍵字的值)：執行下濾操作。
Delete：將堆末尾的值放于刪除的節點處，執行下濾操作。
BuildHeap(構建堆):
1.執行N次Insert操作。總運行時間為O(N)。
2.從堆末尾節點的父節點開始，向根的方向，依次執行下濾操作。總運行時間為O(N)。
代碼：
class MinHeap(object): def __init__(self): self.heap=[] self._count=0 def __len__(self): return self._count def insert(self,key): self.heap.append(key) self._count+=1 self._up(self._count-1) def deleteMin(self): a=self.heap.pop() self.heap[0]=a self._count-=1 self._down(0) def _up(self,i): if i>0: parent=(i-1)/2 if self.heap[parent]>self.heap[i]: self.heap[parent],self.heap[i]=self.heap[i],self.heap[parent] self._up(parent) def _down(self,i): left=2*i+1 right=2*i+2 small=i if left<self._count and self.heap[i]>self.heap[left]: small=left if right<self._count and self.heap[right]<self.heap[small]: small=right if small!=i: self.heap[i],self.heap[small]=self.heap[small],self.heap[i] self._down(small)
新聞熱點
疑難解答
