摘要: 優(yōu)先級(jí)隊(duì)列

C++博客 Alex-Lee 2009-10-18

上篇隨筆談到了堆結(jié)構(gòu)的一個(gè)應(yīng)用就是堆排序算法，雖然堆排序算法性能不錯(cuò)，但是比起快速排序算法還是有些差距。但是堆結(jié)構(gòu)的另外一個(gè)應(yīng)該就比較廣泛了，就是優(yōu)先級(jí)隊(duì)列。
優(yōu)先級(jí)隊(duì)列有3中操作：插入(O(lgn))，最大最小值(O(1)),刪去最大最小值(O(lgn))。其算法性能很好，在優(yōu)先級(jí)調(diào)度作業(yè)上應(yīng)用比較廣泛。基于優(yōu)先級(jí)的調(diào)度算法中，基于堆結(jié)構(gòu)的實(shí)現(xiàn)算法是一個(gè)比較好選擇。在事件驅(qū)動(dòng)的仿真器中也有應(yīng)用。  閱讀全文