除特別注明外，本站所有文章均為原創(chuàng)，轉(zhuǎn)載請注明地址
一.優(yōu)先隊列的應(yīng)用
優(yōu)先隊列在程序開發(fā)中屢見不鮮，比如操作系統(tǒng)在進行進程調(diào)度時一種可行的算法是使用優(yōu)先隊列，當一個新的進程被fork()出來后，首先將它放到隊列的最后，而操作系統(tǒng)內(nèi)部的Scheduler負責不斷地從這個優(yōu)先隊列中取出優(yōu)先級較高的進程執(zhí)行；爬蟲系統(tǒng)在執(zhí)行時往往也需要從一個優(yōu)先級隊列中循環(huán)取出高優(yōu)先級任務(wù)并進行抓取。可以想見，如果類似這樣的任務(wù)不適用優(yōu)先級進行劃分的話，系統(tǒng)必會出現(xiàn)故障，例如操作系統(tǒng)中低優(yōu)先級進程持續(xù)占用資源而高優(yōu)先級進程始終在隊列中等待。此外，優(yōu)先隊列在貪婪算法中也有一些應(yīng)用。
二.優(yōu)先隊列的實現(xiàn)原理
優(yōu)先隊列的實現(xiàn)方式是使用二叉堆的結(jié)構(gòu)，需要滿足以下兩條性質(zhì)(Heap property)，這里以小頂堆為例講解：
1.任何結(jié)點的值都小于或等于其子節(jié)點的值。
2.所有結(jié)點從上到下，從左到右填入，即一棵完全二叉樹。
基于這兩條規(guī)律，二叉堆在實現(xiàn)中往往會使用一個數(shù)組，下面我們研究一下JDK中二叉堆(優(yōu)先隊列)的實現(xiàn)。
三.優(yōu)先隊列在JDK中的實現(xiàn)方式
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動安全 [無線安全]玩轉(zhuǎn)無線電——不安全的藍牙鎖 2017-07-26
- 消息隊列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標分割】 2017-07-26
- 詞向量-LRWE模型-更好地識別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來看看(二) 2017-07-26
學習是年輕人改變自己的最好方式