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

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

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