優(yōu)先隊(duì)列，其實(shí)我一直不愿承認(rèn)“優(yōu)先隊(duì)列”是一種“隊(duì)列”，現(xiàn)實(shí)世界的隊(duì)列（比如排隊(duì)）告訴我們，隊(duì)列最明顯的性質(zhì)就是先進(jìn)先出。而優(yōu)先隊(duì)列，似乎跟這個(gè)規(guī)則沒什么關(guān)系，出隊(duì)的早晚跟進(jìn)隊(duì)的順序基本沒關(guān)系，而是看誰更有“特權(quán)”。我排隊(duì)排了一大早上，你小子剛來憑什么比我先買到早餐？這簡直太不公平啦！似乎又不是這么回事，一般的隊(duì)列也是有“特權(quán)”的，它的特權(quán)是時(shí)間，誰進(jìn)隊(duì)的時(shí)間久誰就更有特權(quán)；而優(yōu)先隊(duì)列的“特權(quán)”是我們規(guī)定的另一種東西。不去糾結(jié)這個(gè)問題了，我們來看看優(yōu)先隊(duì)列吧。這里用堆實(shí)現(xiàn)優(yōu)先隊(duì)列，只討論入隊(duì)（EnQueue()）和出隊(duì)（Dequeue()），都具有O(logN)的時(shí)間復(fù)雜度。其實(shí)還有一個(gè)很重要的操作：改變隊(duì)列中某個(gè)元素的權(quán)值，這里就不討論了。
關(guān)于堆的操作可以先參閱我前面的文章《堆排序》（http://m.shnenglu.com/hoolee/archive/2012/07/16/183700.html）初始化優(yōu)先隊(duì)列的過程就是建立堆的過程，維護(hù)隊(duì)列的過程就是維護(hù)堆的過程。初始化隊(duì)列：經(jīng)過n/2次篩選（由f()函數(shù)實(shí)現(xiàn)）即可，這里不再贅述。入隊(duì)：入隊(duì)操作先將該元素num加到堆的末尾，為了保持堆（大頂堆）的性質(zhì)，需要將num不斷與父節(jié)點(diǎn)比較，如果num比父節(jié)點(diǎn)大就交換它們。void EnQueue(int *a, int *r, int num) a[]是存放堆的數(shù)組 *r為隊(duì)列的長度，指向堆中的最后一個(gè)元素 num為要加入隊(duì)列的數(shù)字
出隊(duì)：出隊(duì)的操作很簡單，直接將堆頂元素彈出即可，不過為了維護(hù)堆的性質(zhì)，我們還要進(jìn)行一次“篩選”。下面的代碼是先將堆中最后一個(gè)元素賦給堆頂元素，然后進(jìn)行一次篩選。（另一種方式是直接將堆頂元素修改為MIN，然后進(jìn)行一次篩選）