歡迎探討，如有錯(cuò)誤敬請(qǐng)指正
如需轉(zhuǎn)載，請(qǐng)注明出處 http://www.cnblogs.com/nullzx/
1. 優(yōu)先隊(duì)列與索引優(yōu)先隊(duì)列
優(yōu)先隊(duì)列的原理大家應(yīng)該比較熟悉，本質(zhì)上就是利用完全二叉樹的結(jié)構(gòu)實(shí)現(xiàn)以log2n的時(shí)間復(fù)雜度刪除隊(duì)列中的最小對(duì)象（這里以小堆頂為例）。完全二叉樹又可以通過數(shù)組下標(biāo)實(shí)現(xiàn)索引，當(dāng)插入一個(gè)對(duì)象的時(shí)候，利用上浮操作更新最小對(duì)象。當(dāng)刪除堆頂最小對(duì)象時(shí)，將末尾的對(duì)象放置到堆頂上，然后執(zhí)行下沉操作。
優(yōu)先隊(duì)列有一個(gè)缺點(diǎn)，就是不能直接訪問已存在于優(yōu)先隊(duì)列中的對(duì)象，并更新它們。這個(gè)問題在Dijistra算法中就有明顯的體現(xiàn)，有時(shí)候我們需要更新已在隊(duì)列中的頂點(diǎn)的距離。為此就需要設(shè)計(jì)一種新型的數(shù)據(jù)結(jié)構(gòu)來解決這個(gè)問題，這就是本文要介紹的索引優(yōu)先隊(duì)列。
索引優(yōu)先隊(duì)用一個(gè)整數(shù)和對(duì)象進(jìn)行關(guān)聯(lián)，當(dāng)我們需要跟新該對(duì)象的值時(shí)，可以通這個(gè)整數(shù)進(jìn)行快速索引，然后對(duì)對(duì)象的值進(jìn)行更新。當(dāng)然更新后的對(duì)象在優(yōu)先隊(duì)列中的位置可能發(fā)生變化，這樣以保證整個(gè)隊(duì)列還是一個(gè)優(yōu)先隊(duì)列。
簡(jiǎn)易版的索引優(yōu)先隊(duì)列API
IndexPriorityQueue<T> | |
IndexPriorityQueue(int capacity, Comparator<T> cmp) | 構(gòu)造函數(shù)，capacity表示隊(duì)列容量，cmp表示對(duì)象的比較器 |
