前面學(xué)習(xí)過隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)是先進(jìn)先出，但有時(shí)候會(huì)出現(xiàn)特殊情況，比如在我們排隊(duì)買票時(shí)，會(huì)有軍人優(yōu)先、老人優(yōu)先等，當(dāng)碰到軍人買票時(shí)，得讓他們優(yōu)先購買，這就破壞了先進(jìn)先出的結(jié)構(gòu)，導(dǎo)致出現(xiàn)了另外一種數(shù)據(jù)結(jié)構(gòu)，就是今天需要整理的優(yōu)先隊(duì)列。

概念

優(yōu)先隊(duì)列也稱為堆，是指在隊(duì)列中，具有優(yōu)先級(jí)特性的元素，最先出隊(duì)的元素。出隊(duì)和入隊(duì)的順序無關(guān)，跟優(yōu)先級(jí)相關(guān)。

優(yōu)先隊(duì)列表示方法

優(yōu)先隊(duì)列可以使用一種中做二叉樹的結(jié)果來保存堆中的數(shù)據(jù)，被稱作為二叉堆，二叉堆是一棵完全二叉樹。所以我們可以使用數(shù)組來表示優(yōu)先隊(duì)列。對(duì)于數(shù)組中任一位置i上的元素，其左兒子在位置2i上，右兒子在（2i+1）上，它的父新則在位置i/2上。以下是一個(gè)優(yōu)先隊(duì)列，并通過數(shù)組來表示它。

堆.jpeg

優(yōu)先隊(duì)代碼實(shí)現(xiàn)

下面通過簡(jiǎn)單的代碼來實(shí)現(xiàn)優(yōu)先隊(duì)列。

function Heap() {
    var items = [];
    /*
    * 判斷是否為空
    * */
    this.isEmpty = function () {
        return items.length === 0;
    }

    /*
    * 返回堆的大小
    * */
    this.size = function () {
        return items.length;
    }

    /*
    * 返回父節(jié)點(diǎn)的索引值
    * */
    this.parentNode = function (index) {
        if(index !== 0){
            return parseInt((index - 1)/2);
        }
        return -1;
    }

    /*
    * 返回左孩子節(jié)點(diǎn)的索引值
    * */
    this.leftChild = function (index) {
        return 2*index + 1;
    }

    /*
    * 返回右孩子節(jié)點(diǎn)的索引值
    * */
    this.rightChild = function (index) {
        return 2*index + 2;
    }

    /*
    * 向堆 中插入元素
    * */
    this.insert = function (data) {
        items.push(data);
        this.siftUp(items.length - 1);
    }
    
    /*
    * 上浮
    * */
    this.siftUp = function (index) {
        var parentIndex = this.parentNode(index);
        while (index > 0 && items[index] > items[parentIndex]){
            var temp = items[parentIndex];
            items[parentIndex] = items[index];
            items[index] = temp;
            index = parentIndex;
        }
    }

    /*
    * 刪除最大元素
    * 1：取出最大元素
    * 2：用最小元素替換最大元素
    * 3：刪除最小位置的數(shù)
    * 4：作用下沉操作重新構(gòu)造堆
    * */
    this.deleteMax = function () {
        if(items.length === 0){
            return null;
        }
        var max = items[0];
        var last = items[items.length - 1];
        items[0] = last;
        items[items.length - 1] = max;
        items.pop();
        this.siftDown(0)

        return max;
    }

    /*
    * 下沉
    * */
    this.siftDown = function (index) {
        while (this.leftChild(index) < items.length){
            var leftIndex = this.leftChild(index);//找出左節(jié)點(diǎn)索引位置
            if(leftIndex + 1 < items.length && items[leftIndex + 1] > items[leftIndex]){//有右節(jié)點(diǎn)，并且右節(jié)點(diǎn)大于左節(jié)點(diǎn)時(shí)，替換成右節(jié)點(diǎn)
                leftIndex ++;
            }
            if(items[index] >= items[leftIndex]){
                break;
            }
            // 交換
            var temp = items[index];
            items[index] = items[leftIndex];
            items[leftIndex] = temp;
            index = leftIndex;
        }
    }

    this.print = function () {
        console.log(JSON.stringify(items));
    }
}

具體的代碼可以在源碼中進(jìn)行查看
個(gè)人博客