1.優先級隊列定義:
優先級隊列（priority queue） 是0個或多個元素的集合，每個元素都有一個優先權，對優先級隊列執行的操作有
（1）查找
（2）插入一個新元素
（3）删除 一般情況下，查找操作用來搜尋優先權最大的元素，删除操作用來删除該元素 。
對于優先權相同的元素，可按先進先出次序處理或按任意優先權進行。
2.優先級隊列的實作方案
優先級隊列的實作既要兼顧成本，也要兼顧效率
(1).第一種使用向量實作:
由圖可知,在使用插入操作時，時間複雜度為o(1),但是在getMax,需要周遊整個向量,找出最大的元素,
而delMax操作時卻不僅要周遊向量找到最大元素,而且在摘抄它之後将所有元素順序後移,這種時間複雜度是無法接受的。
(2).使用有序向量
在使用有序向量時,getMax操作和delMax操作都隻有常數時間,但是在插入操作時,先要對其進行二分查找,找到插入的位置,然後在提前将它的後繼依次後移,維護有序向量的有序性.這種方式時間複雜度太高,無法接受。
(3).使用清單
在使用清單建構優先級隊列時,insert操作隻需在隊尾将指針指向待插入元素。但是在getMax操作中,需要周遊整個清單。而在delMax操作時,先要找到最大值元素,然後在将前驅的指針指向後繼,完成删除操作。是以這種方式時間複雜度較高。
(4)使用有序清單
在使用有序向量時,也面臨着時間複雜度較高的情況。在進行insert操作時,需要找到待插入元素的前驅,然後将前驅的指針指向自己,自己的指針指向後繼。
（5）使用BBST
使用BBST建構優先級隊列時，無論是插入，查找還是删除，都有非常優秀，但是優先級隊列卻不需要使用到全部的BBST。
（6）使用堆來實作優先級隊列
堆是一種實體結構上用數組實作，邏輯結構為一顆完全二叉樹的資料結構。堆的定義是父節點元素必定大于（小于）它的左孩子節點或者右孩子節點，（大于為大根堆，小于為小根堆）這樣根節點元素則必然是整個堆的最大（最小）值。
以下是一個值為,1.2.3.4.5的小根堆的構成（因為我找到不到如何設定成大根堆.不過原理是一樣的）
由圖可知堆的邏輯結構和實體結構，下面給出具體的代碼實作
3.具體實作
首先先給出它的insert操作
def insert(self,value):
self._arr.append(value) #将新值插入到堆尾
self._index += 1 #index++ index代表了value的下标
index=self._index
if index % 2 == 0:
parent = index // 2 - 1
else:
parent = index // 2 #擷取index的父節點
temp=self._arr[index] #擷取value的值
#上濾
while parent>=0: #如果沒超過根節點 也就是index的父節點最大隻能為0号下标
if temp<self._arr[parent]: #如果下标index的值也就是value小于它的父節點，沒破壞堆序性
break
#print(index,parent)
self._arr[index] = self._arr[parent]#不然的話将它的父節點的值賦給index
index=parent #index的父節點成為新的待調整結點
if index%2==0:
parent = index // 2-1
else:
parent=index//2#取得新index的父節點
self._arr[index]=temp#循環結束後将temp也就是value的值給最後停下來的index
return
getMax操作
def getMax(self):
if self._index == -1: #如果_index為-1 則堆為空
return
self.__swap(0,self._index,self._arr)#不然交換堆頂元素和最後的元素
maxValue=self._arr[self._index] #交換後取得最後一個元素
self.__remove() #删除最後一個元素
return maxValue #傳回最大值
remove操作
def __remove(self):
if self._index==-1: #如果_index為-1 則堆為空
return
self._arr.pop() #删除最後一個元素
self._index-=1
self.buildHeap(0,self._arr)#因為目前堆頂元素是未知的，是以要進行一次調整
return
調整操作
def buildHeap(self,index,_arr):
if self._index==-1: #如果堆裡沒有原始 則傳回
return
temp=_arr[index]#temp代表index下标的值
k=(index*2)+1 #k代表index的左子樹
lenth=len(_arr)-1
while k<=lenth:
if k<lenth and _arr[k]<_arr[k+1] :#如果k的左子樹小于length（也就是k還有右子樹）并且它的右子樹大于它
k+=1 #k++ k指向了右子樹
if _arr[k]<temp: #如果temp大于目前子樹的最大值（無論左子樹還是右子樹都大于，因為上個判斷已經判斷了左右子樹大小)
break #直接傳回
_arr[index]=_arr[k] #如果temp不大于左子樹或者右子樹的值 将K結點（index子樹）的值賦給inedx結點值
index=k #要調整的結點變為K 因為index結點已經判斷完了
k=(k*2)+1 #K變成index的左子樹
_arr[index]=temp #如果循環結束，說明調整完畢，最後index的值是将是它的子樹的值，需要修改為value也就是temp的值
測試結果
輸入:
l=[11,2,3,4,5,6]
pq=PriorityQueue()
print('目前堆元素為',pq.get_arr())
print('擷取最大值',pq.getMax())
print('目前堆元素為',pq.get_arr())
pq.insert(14)
print('目前堆元素為',pq.get_arr())
print('擷取的最大值',pq.getMax())
print('擷取的最大值',pq.getMax())
print('目前堆元素為',pq.get_arr())
輸出:
目前堆元素為 [11, 5, 6, 4, 2, 3]
擷取最大值 11
目前堆元素為 [6, 5, 3, 4, 2]
目前堆元素為 [14, 5, 6, 4, 2, 3]
擷取的最大值 14
擷取的最大值 6
目前堆元素為 [5, 4, 3, 2]
程序已結束,退出代碼0
完整版代碼
#優先級隊列 2018-01-06
class PriorityQueue:
_arr=[]
_index=-1
def __init__(self,arr=[]):
self._arr=arr
self._index=len(self._arr)-1#指向最後一個元素
self.firstBuildHeap()
#index代表要進行向下調整的結點
def buildHeap(self,index,_arr):
if self._index==-1: #如果堆裡沒有原始 則傳回
return
temp=_arr[index]#temp代表index下标的值
k=(index*2)+1 #k代表index的左子樹
lenth=len(_arr)-1
while k<=lenth:
if k<lenth and _arr[k]<_arr[k+1] :#如果k的左子樹小于length（也就是k還有右子樹）并且它的右子樹大于它
k+=1 #k++ k指向了右子樹
if _arr[k]<temp: #如果temp大于目前子樹的最大值（無論左子樹還是右子樹都大于，因為上個判斷已經判斷了左右子樹大小)
break #直接傳回
_arr[index]=_arr[k] #如果temp不大于左子樹或者右子樹的值 将K結點（index子樹）的值賦給inedx結點值
index=k #要調整的結點變為K 因為index結點已經判斷完了
k=(k*2)+1 #K變成index的左子樹
_arr[index]=temp #如果循環結束，說明調整完畢，最後index的值是将是它的子樹的值，需要修改為value也就是temp的值
def firstBuildHeap(self):
index=(len(self._arr)//2)-1
while index>=0:
self.buildHeap(index,self._arr)
index-=1
def get_arr(self):
return self._arr
def getMax(self):
if self._index == -1: #如果_index為-1 則堆為空
return
self.__swap(0,self._index,self._arr)#不然交換堆頂元素和最後的元素
maxValue=self._arr[self._index] #交換後取得最後一個元素
self.__remove() #删除最後一個元素
return maxValue #傳回最大值
def __remove(self):
if self._index==-1: #如果_index為-1 則堆為空
return
self._arr.pop() #删除最後一個元素
self._index-=1
self.buildHeap(0,self._arr)#因為目前堆頂元素是未知的，是以要進行一次調整
return
def insert(self,value):
self._arr.append(value) #将新值插入到堆尾
self._index += 1 #index++ index代表了value的下标
index=self._index
if index % 2 == 0:
parent = index // 2 - 1
else:
parent = index // 2 #擷取index的父節點
temp=self._arr[index] #擷取value的值
#上濾
while parent>=0: #如果沒超過根節點 也就是index的父節點最大隻能為0号下标
if temp<self._arr[parent]: #如果下标index的值也就是value小于它的父節點，沒破壞堆序性
break
#print(index,parent)
self._arr[index] = self._arr[parent]#不然的話将它的父節點的值賦給index
index=parent #index的父節點成為新的待調整結點
if index%2==0:
parent = index // 2-1
else:
parent=index//2#取得新index的父節點
self._arr[index]=temp#循環結束後将temp也就是value的值給最後停下來的index
return
def __swap(self,i,j,arr):
k=arr[i]
arr[i]=arr[j]
arr[j]=k