優(yōu)先隊列，其實我一直不愿承認“優(yōu)先隊列”是一種“隊列”，現(xiàn)實世界的隊列（比如排隊）告訴我們，隊列最明顯的性質就是先進先出。而優(yōu)先隊列，似乎跟這個規(guī)則沒什么關系，出隊的早晚跟進隊的順序基本沒關系，而是看誰更有“特權”。我排隊排了一大早上，你小子剛來憑什么比我先買到早餐？這簡直太不公平啦！
似乎又不是這么回事，一般的隊列也是有“特權”的，它的特權是時間，誰進隊的時間久誰就更有特權；而優(yōu)先隊列的“特權”是我們規(guī)定的另一種東西。
不去糾結這個問題了，我們來看看優(yōu)先隊列吧。
這里用堆實現(xiàn)優(yōu)先隊列，只討論入隊（EnQueue()）和出隊（Dequeue()），都具有O(logN)的時間復雜度。其實還有一個很重要的操作：改變隊列中某個元素的權值，這里就不討論了。

關于堆的操作可以先參閱我前面的文章《堆排序》（http://m.shnenglu.com/hoolee/archive/2012/07/16/183700.html）
初始化優(yōu)先隊列的過程就是建立堆的過程，維護隊列的過程就是維護堆的過程。
初始化隊列：
經過n/2次篩選（由f()函數(shù)實現(xiàn)）即可，這里不再贅述。
入隊：
入隊操作先將該元素num加到堆的末尾，為了保持堆（大頂堆）的性質，需要將num不斷與父節(jié)點比較，如果num比父節(jié)點大就交換它們。
void EnQueue(int *a, int *r, int num)
    a[]是存放堆的數(shù)組
    *r為隊列的長度，指向堆中的最后一個元素
    num為要加入隊列的數(shù)字

void EnQueue(int *a, int *r, int num)
{
    (*r)++;
    a[*r] = num;
    int i = *r;
    while(1)
    {
        if(i > 1 && a[i] > a[i / 2])
        {//如果i不是堆頂，并且該節(jié)點>父節(jié)點
            swap(&a[i], &a[i / 2]);
            i /= 2;
        }
        else 
            break;
    }
}

出隊：
出隊的操作很簡單，直接將堆頂元素彈出即可，不過為了維護堆的性質，我們還要進行一次“篩選”。下面的代碼是先將堆中最后一個元素賦給堆頂元素，然后進行一次篩選。（另一種方式是直接將堆頂元素修改為MIN，然后進行一次篩選）

int DeQueue(int *a, int *r)
{
    int t = a[1];
    a[1] = a[*r];
    (*r)--;
    f(a, 1, *r);
    return t;
}