序誘導的整數優(yōu)先級隊列的算法及類庫實現.pdf

1、優(yōu)先級隊列在眾多領域有著廣泛的應用，尤其是在離散事件系統(tǒng)仿真(DESS)中。傳統(tǒng)的隱式堆結構難以滿足實時性較高的DESS軟件的要求，而整數優(yōu)先級隊列由于其效率和特殊性非常適合作為此類仿真軟件的事件組織結構。
　　 本文首先介紹了一個基于整數優(yōu)先級隊列的簡單仿真實例，通過對該系統(tǒng)的整數化合理地建立了系統(tǒng)模型，由此給出了仿真系統(tǒng)的簡要設計，進而系統(tǒng)討論了該系統(tǒng)所需要的幾種常見序誘導整數優(yōu)先級隊列：有限整數優(yōu)先級隊列、可擴展整數優(yōu)先級

2、隊列和定界整數優(yōu)先級隊列，并分析了這些結構的最壞情況時間復雜度和分攤時間復雜度。
　　 本文針對整數優(yōu)先級隊列的特點，完成了如下工作：通過提煉上濾和下濾操作，設計并精化了有限整數優(yōu)先級隊列的類庫；對相鄰堆疊予以連續(xù)存儲，從而改進了堆疊式擴展存儲方案并提升了操作效率；給出了二項堆的結合建堆算法；設計了van Emde Boas樹的整體建堆算法；用過半數選擇算法改進了多鍵排序算法，并將其應用于低熵情況下的多鍵整數優(yōu)先級隊列建堆算法。