Priority queue - 優先隊列
相關概念
Priority queue優先隊列是一種用來維護由一組元素構成的集合S的資料結構，
其中的每一種元素都有一個相關的值,稱為關鍵字（key）。
一個最大有限隊列支援一下操作:
insert(S,x):把元素x插入到集合S中.
maximum(S):傳回集合S中具有最大關鍵字的元素.
extract_max(S):去掉并傳回S中具有最大關鍵字的元素
increase_key(S,x,k):将集合S中的元素x的關鍵字值增加到k,這裡假設k的值不小于x元素原來的關鍵字的值
最大優先隊列的應用有很多,其中一個就是在共享計算機系統的作業排程.最大優先隊列記錄将要執行的各個作業以及他們之間的相對優先級. 當一個作業完成或者被中斷後,排程器調用extract_max(S)，從所有作業中,選優具有最高優先級的作業來執行. 在任何時候,排程器都可以調用insert把一個新的作業加入到隊列中.
相應地,最小優先隊列支援的操作包括:insert,minimum,extract_min和decrease_key.最小優先隊列可以被用于基于事件驅動的模拟器.隊列中儲存要模拟的事件,每個事件都有一個發生時間作為其關鍵字.
事件必須按照發生的時間順序進行模拟,因為某一事件的模拟結果可能會觸發其他事件的模拟. 在每一步,模拟程式調用extract_min來獲得下一個要模拟的事件.當一個新事件産生時,模拟器通過調用insert将其插入到最小優先級隊列中.
優先隊列可以用堆來實作.對一個像作業排程或時間驅動模拟器這樣的程式來說,優先隊列的元素對應着應用程式中的對象. Python programming
# 優先隊列是基于最大堆實作的.
import heap_sorting # heap_sorting 子產品代碼位于： https://www.cnblogs.com/zzyzz/p/12869256.html
def heap_maximum(A):
return A[0]
def heap_extract_max(A, heap_size): # heap_size 是堆的一個屬性, 這裡通過一個函數參數的形式實作.
if heap_size < 1:
print('error - heap underflow')
return False
max = A.pop(0)
heap_size -= 1
heap_sorting.max_heapify(A,1,heap_size)
return max
if __name__ == '__main__':
A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
print('Before', A)
heap_extract_max(A, 10)
print('After', A)
結果列印:
Before [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
After [14, 10, 8, 7, 9, 3, 2, 4, 1] def heap_increase_key(A, i, key):
if key < A[i-1]:
print('error - new key is smaller than current key')
return False
# 最大堆 A 中的第 i 個元素 A[i-1] 首先被替換成待插入的元素 key
A[i-1] = key
# 新插入的元素會不斷地與其父結點進行比較, 如果目前元素 key 比較大, 則與其父結點進行交換, 更新 i 的值後繼續比較. 直到目前元素 key 小于其父結點的時候終止循環.
while i > 1 and A[heap_sorting.parent(i)-1] < A[i-1]:
print(A[heap_sorting.parent(i) - 1], A[i - 1])
A[i-1], A[heap_sorting.parent(i)-1] = A[heap_sorting.parent(i)-1], A[i-1]
i = heap_sorting.parent(i)
print('i',i)
print('A',A)
if __name__ == '__main__':
A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
print('Before', A)
heap_increase_key(A,9,15) # 将 15 插入到最大堆 A 中. 然後加工新的數組為新的最大堆.
print('After', A)
Before [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
8 15 # 第一次循環的 parent 和 key
i 4 # parent < key, 更新 i
A [16, 14, 10, 15, 7, 9, 3, 2, 8, 1] # 第一次循環後得到的新數組
14 15 # 第二次循環的 parent 和 key
i 2 # parent < key, 更新 i
A [16, 15, 10, 14, 7, 9, 3, 2, 8, 1] # # 第二次循環後得到的新數組
After [16, 15, 10, 14, 7, 9, 3, 2, 8, 1] # 循環退出後的得到新數組即為新的最大堆
Algorithms - Priority Queue - 優先隊列 def max_heap_insert(A, key, heap_size):
heap_size += 1
A.insert(heap_size-1, -float('inf'))
print(A)
heap_increase_key(A, heap_size, key)
if __name__ == '__main__':
A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
print('Before', A)
max_heap_insert(A,13,10)
print('After', A)
結果列印:
Before [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1, -inf] # 先在對應的位置上設定一個 sentinel
7 13 # parent < key
i 5 # 交換 parent 和 key 後更新 i
A [16, 14, 10, 8, 13, 9, 3, 2, 4, 1, 7] # 交換後新的數組
After [16, 14, 10, 8, 13, 9, 3, 2, 4, 1, 7] # 循環退出後的結果 Reference,
1. Introduction to algorithms