歡迎探討，如有錯誤敬請指正

如需轉(zhuǎn)載，請注明出處 http://www.cnblogs.com/nullzx/

1. 優(yōu)先隊列與索引優(yōu)先隊列

優(yōu)先隊列的原理大家應(yīng)該比較熟悉，本質(zhì)上就是利用完全二叉樹的結(jié)構(gòu)實(shí)現(xiàn)以log2n的時間復(fù)雜度刪除隊列中的最小對象（這里以小堆頂為例）。完全二叉樹又可以通過數(shù)組下標(biāo)實(shí)現(xiàn)索引，當(dāng)插入一個對象的時候，利用上浮操作更新最小對象。當(dāng)刪除堆頂最小對象時，將末尾的對象放置到堆頂上，然后執(zhí)行下沉操作。

優(yōu)先隊列有一個缺點(diǎn)，就是不能直接訪問已存在于優(yōu)先隊列中的對象，并更新它們。這個問題在Dijistra算法中就有明顯的體現(xiàn)，有時候我們需要更新已在隊列中的頂點(diǎn)的距離。為此就需要設(shè)計一種新型的數(shù)據(jù)結(jié)構(gòu)來解決這個問題，這就是本文要介紹的索引優(yōu)先隊列。

索引優(yōu)先隊用一個整數(shù)和對象進(jìn)行關(guān)聯(lián)，當(dāng)我們需要跟新該對象的值時，可以通這個整數(shù)進(jìn)行快速索引，然后對對象的值進(jìn)行更新。當(dāng)然更新后的對象在優(yōu)先隊列中的位置可能發(fā)生變化，這樣以保證整個隊列還是一個優(yōu)先隊列。

簡易版的索引優(yōu)先隊列API

網(wǎng)友評論

IndexPriorityQueue<T>


IndexPriorityQueue(int capacity, Comparator<T> cmp)

構(gòu)造函數(shù)，capacity表示隊列容量，cmp表示對象的比較器