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