序誘導(dǎo)的整數(shù)優(yōu)先級隊列的算法及類庫實現(xiàn).pdf

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

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