除特別注明外，本站所有文章均為原創(chuàng)，轉(zhuǎn)載請(qǐng)注明地址
一.優(yōu)先隊(duì)列的應(yīng)用
優(yōu)先隊(duì)列在程序開發(fā)中屢見不鮮，比如操作系統(tǒng)在進(jìn)行進(jìn)程調(diào)度時(shí)一種可行的算法是使用優(yōu)先隊(duì)列，當(dāng)一個(gè)新的進(jìn)程被fork()出來后，首先將它放到隊(duì)列的最后，而操作系統(tǒng)內(nèi)部的Scheduler負(fù)責(zé)不斷地從這個(gè)優(yōu)先隊(duì)列中取出優(yōu)先級(jí)較高的進(jìn)程執(zhí)行；爬蟲系統(tǒng)在執(zhí)行時(shí)往往也需要從一個(gè)優(yōu)先級(jí)隊(duì)列中循環(huán)取出高優(yōu)先級(jí)任務(wù)并進(jìn)行抓取?？梢韵胍?，如果類似這樣的任務(wù)不適用優(yōu)先級(jí)進(jìn)行劃分的話，系統(tǒng)必會(huì)出現(xiàn)故障，例如操作系統(tǒng)中低優(yōu)先級(jí)進(jìn)程持續(xù)占用資源而高優(yōu)先級(jí)進(jìn)程始終在隊(duì)列中等待。此外，優(yōu)先隊(duì)列在貪婪算法中也有一些應(yīng)用。
二.優(yōu)先隊(duì)列的實(shí)現(xiàn)原理
優(yōu)先隊(duì)列的實(shí)現(xiàn)方式是使用二叉堆的結(jié)構(gòu)，需要滿足以下兩條性質(zhì)(Heap property)，這里以小頂堆為例講解：
1.任何結(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值。
2.所有結(jié)點(diǎn)從上到下，從左到右填入，即一棵完全二叉樹。
基于這兩條規(guī)律，二叉堆在實(shí)現(xiàn)中往往會(huì)使用一個(gè)數(shù)組，下面我們研究一下JDK中二叉堆(優(yōu)先隊(duì)列)的實(shí)現(xiàn)。
