1. 介紹

優(yōu)先隊(duì)列就是在我們插入一個(gè)元素的同時(shí)，賦予它一個(gè)優(yōu)先級(jí)。相比于普通的隊(duì)列，優(yōu)先隊(duì)列在有更廣泛的用途。

比如在系統(tǒng)資源調(diào)度上，主程序就要比輔程序有更高的優(yōu)先級(jí)，不然當(dāng)內(nèi)存不夠用時(shí)，主程序可能就會(huì)面臨被殺死以釋放內(nèi)存的風(fēng)險(xiǎn)。在現(xiàn)實(shí)生活中，優(yōu)先隊(duì)列的思想也被廣泛應(yīng)用，比如在公交車(chē)上，一般老弱病殘就擁有較高的優(yōu)先級(jí)。

講完了概念，下面就來(lái)看看怎么去實(shí)現(xiàn)優(yōu)先隊(duì)列。

2. 簡(jiǎn)單實(shí)現(xiàn)

所謂簡(jiǎn)單實(shí)現(xiàn)，也就是說(shuō)我們采用順序插入的方式去實(shí)現(xiàn)優(yōu)先隊(duì)列。當(dāng)插入一個(gè)元素的時(shí)候，我們所要做的工作基本如下：

1. 檢查當(dāng)前隊(duì)列是否為空，如果為空直接插入數(shù)組，否則進(jìn)行下一步。

2. 從頭到尾比較新插入元素與隊(duì)列中各元素的優(yōu)先級(jí)，直到找到一個(gè)比新插入元素優(yōu)先級(jí)更小的，將新元素插入到當(dāng)前位置，如果沒(méi)找到，則進(jìn)行下一步。

3. 如果到了第三步，說(shuō)明當(dāng)前隊(duì)列非空而且隊(duì)列中的元素優(yōu)先級(jí)都高于新插入元素，這個(gè)時(shí)候我們將新元素插入到隊(duì)列末尾即可。

了解了基本思想，下面就來(lái)看一下代碼 ：

this.enqueue = function(element, priority) {
    var item = new QueueElement(element, priority);

    if(this.isEmpty()) {
        items.push(item);
    } else {
        var added = false,
            length = this.size();

        for(var i = 0; i < length; i++) {
            if(items[i].priority < item.priority) {
                items.splice(i,0,item);
                added = true;
                break;
            }
        }

        if(!added) {
            items.push(item);
        } 
    }
};

可見(jiàn)，實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列的確很簡(jiǎn)單，不過(guò)上面這種簡(jiǎn)單的實(shí)現(xiàn)，好像算法的效率并不高，因?yàn)?splice() 方法的效率并不高，關(guān)于 splice() 方法實(shí)現(xiàn)原理，你可以參考 splice方法實(shí)現(xiàn)原理分析 一文。

既然如此，我們可能想到了，一般涉及到大量插入和刪除的時(shí)候，我們會(huì)選擇鏈表，這的確是一個(gè)好的選擇，下面我們就來(lái)看看用鏈表來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列。

3. 基于鏈表的優(yōu)先隊(duì)列

為了使用鏈表來(lái)保存對(duì)象，首先我們需要自定義一個(gè) Node 類(lèi)。

function Node(element, priority) {
    this.element = element;
    this.priority = priority;
    this.next = null;
}

當(dāng)然，你也可以將這個(gè)隊(duì)列定義成雙向指針，這樣操作起來(lái)可能更容易理解一些。不過(guò)為了方便，我使用了單向的鏈表。

基本思想和上面的一樣，下面我們看一下具體實(shí)現(xiàn)代碼。

this.enqueue = function(element, priority) {
    var item = new Node(element, priority),
        current = head;

    if (this.isEmpty()) {
        head = item;
    } else if (head.priority < item.priority) {
        item.next = head;
        head = item;
    } else {
        var added = false;
        while (current) {
            if (current.priority < item.priority) {
                item.next = current.next;
                current.next = item;
                break;
            } else {
                if (current.next == null) {
                    current.next = item;
                }
                current = current.next;
            }
        }
    }

    length++;
};

當(dāng)一個(gè)元素入隊(duì)時(shí)，首先的步驟主要如下：

1. 如果當(dāng)前鏈表為空，則直接將頭結(jié)點(diǎn)指向插入元素即可。

2. 如果插入的節(jié)點(diǎn)優(yōu)先級(jí)比頭結(jié)點(diǎn)還要高，那么直接將要插入元素的 next 指針指向頭指針，然后將頭指針直接賦值。

3. 如果上述兩種情況都不符合，那就開(kāi)始逐個(gè)遍歷元素，如果找到了比要插入元素優(yōu)先級(jí)低的已入隊(duì)元素，那就將要插入的元素放下來(lái)，這個(gè)時(shí)候只需要改變兩次指針指向即可。

4. 值得注意的是，我們需要判斷要插入元素如果需要放置在尾節(jié)點(diǎn)，那么將不得不進(jìn)行 current.next === null 的判斷。

讓我們來(lái)比較以下利用鏈表與不用鏈表的差別在哪里，插入元素時(shí)，不使用鏈表和使用鏈表都需要經(jīng)過(guò) N 次比較，但是如果移動(dòng)元素的話，那么使用鏈表的時(shí)間復(fù)雜度為 O(1), 不使用鏈表的話則為 O(N) 。

雖然使用鏈表已經(jīng)使優(yōu)先隊(duì)列得到了優(yōu)化，不過(guò)這還遠(yuǎn)遠(yuǎn)不夠，一般如果我們想到優(yōu)化性能時(shí)，都會(huì)情不自禁的想到樹(shù)，因?yàn)閷?duì)于一個(gè)用于 N 個(gè)節(jié)點(diǎn)的二叉樹(shù)而言，僅有 lgN 層，這樣的話就有可能讓我們的算法性能大幅度提升。下面我們就用堆這中數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列。

4. 堆結(jié)構(gòu)的優(yōu)先隊(duì)列

當(dāng)一顆二叉樹(shù)的每個(gè)節(jié)點(diǎn)都大于或小于它的兩個(gè)子節(jié)點(diǎn)的時(shí)候，它被稱(chēng)之為堆。

當(dāng)根節(jié)點(diǎn)的值大于它的兩個(gè)子節(jié)點(diǎn)的時(shí)候，稱(chēng)之為大根堆，反之成為小根堆。

一般用完全二叉樹(shù)表達(dá)堆，因?yàn)樗幸恍┮子谖覀兙幊痰男再|(zhì)。

若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)。

我們可以用數(shù)組來(lái)存儲(chǔ)完全二叉樹(shù)，不過(guò)一般我們從數(shù)組下標(biāo)為 1 開(kāi)始使用，因?yàn)檫@樣的話，就可以輕松的算出一個(gè)根節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)被放置在哪個(gè)位置。比如對(duì)于第 1 個(gè)元素，它的左子節(jié)點(diǎn)的坐標(biāo)就是 (2 * 1), 它的右子節(jié)點(diǎn)的坐標(biāo)就是 (2 * 1 + 1)。

為了完成功能，我首先寫(xiě)了兩個(gè)輔助函數(shù)，less() 用于比較優(yōu)先級(jí)，exch 用于交換兩個(gè)元素的位置。

var less = function(i, j) {
    if(items[i].priority < items[j].priority) {
        return true;
    }
    return false;
};

var exch = function(i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
};

下面就來(lái)介紹兩個(gè)核心的函數(shù)，swim() 和 sink()。

this.swim = function(k) {
    while (k > 1 && less(Math.floor(k / 2), k)) {
        exch(Math.floor(k / 2), k);
        k = Math.floor(k / 2);
    }
};

當(dāng)我們?cè)跀?shù)組中插入一個(gè)新的元素時(shí)，一般將元素插入到數(shù)組末尾，然后調(diào)用 swim() 將元素上浮到其應(yīng)在的位置，這個(gè)函數(shù)的執(zhí)行步驟如下：

1. 當(dāng)前下標(biāo)如果小于等于 1， 則直接退出函數(shù)，因?yàn)檫@時(shí)元素已經(jīng)在第一的位置，記住我們是從下標(biāo) 1 開(kāi)始存入元素的。

2. 如果當(dāng)前位置的元素大于其父元素，則交換位置，并重置下標(biāo)繼續(xù)執(zhí)行循環(huán)語(yǔ)句。

swim() 函數(shù)總能保證一個(gè)剛插入的元素找到它的最終位置。不過(guò)值得注意的是在 JavaScript 中我們不得不利用 Math.floor() 確保每次運(yùn)算得到的下標(biāo)都是一個(gè)整數(shù)。

this.sink = function(k) {
    while(2 * k <= length) {
        var j = 2 * k;
        if(j < length && less(j, j+1)) {
            j++;
        }

        if(!less(k, j)) {
            break;
        }

        exch(k, j);
        k = j;
    }
};

當(dāng)我們刪除了一個(gè)元素之后，我們需要在刪除節(jié)點(diǎn)的子節(jié)點(diǎn)中找到一個(gè)去頂替它，sink() 函數(shù)就是為了保證我們?cè)趧h除元素的時(shí)候整個(gè)堆仍然是有序的，其工作步驟主要如下：

當(dāng)下標(biāo)為 k 的元素仍有子節(jié)點(diǎn)時(shí)， 尋找其左右子節(jié)點(diǎn)中優(yōu)先級(jí)高的那一個(gè)，如果較高的那一個(gè)比 k 的優(yōu)先級(jí)高，則交換位置，否則直接跳出循環(huán)。

好了，兩個(gè)核心的函數(shù)介紹完畢了，下面來(lái)看看如果在隊(duì)列中插入元素的方法。

this.enqueue = function(element, priority) {
    var item = new Item(element, priority);

    items[++length] = item;
    swim(length);
};

值得提醒的是，由于在完全二叉樹(shù)中并沒(méi)有要求左子樹(shù)和右字?jǐn)?shù)之間的大小需要滿(mǎn)足什么關(guān)系，所以你在打印結(jié)果的時(shí)候看到的并不是一個(gè)有序的集合。不過(guò)能夠保證的是你每次彈出的元素其優(yōu)先級(jí)一定是最高的。

this.dequeue = function() {
    var max = items[1];
    exch(1, length--);
    items[length + 1] = null;
    sink(1);
    return max;
};

在彈出隊(duì)列時(shí)，我們將最后一個(gè)元素與第一個(gè)優(yōu)先級(jí)最高的元素進(jìn)行交換，然后重新調(diào)用 sink() 恢復(fù)堆的有序性。

你可以在 我的 Github 查看源碼～