前面学习过队列这种数据结构，该数据结构的特点是先进先出，但有时候会出现特殊情况，比如在我们排队买票时，会有军人优先、老人优先等，当碰到军人买票时，得让他们优先购买，这就破坏了先进先出的结构，导致出现了另外一种数据结构，就是今天需要整理的优先队列。

概念

优先队列也称为堆，是指在队列中，具有优先级特性的元素，最先出队的元素。出队和入队的顺序无关，跟优先级相关。

优先队列表示方法

优先队列可以使用一种中做二叉树的结果来保存堆中的数据，被称作为二叉堆，二叉堆是一棵完全二叉树。所以我们可以使用数组来表示优先队列。对于数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在（2i+1）上，它的父新则在位置i/2上。以下是一个优先队列，并通过数组来表示它。

优先队代码实现

下面通过简单的代码来实现优先队列。

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

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

    /*
    * 返回父节点的索引值
    * */
    this.parentNode = function (index) {
        if(index !== 0){
            return parseInt((index - 1)/2);
        }
        return -1;
    }

    /*
    * 返回左孩子节点的索引值
    * */
    this.leftChild = function (index) {
        return 2*index + 1;
    }

    /*
    * 返回右孩子节点的索引值
    * */
    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：删除最小位置的数
    * 4：作用下沉操作重新构造堆
    * */
    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);//找出左节点索引位置
            if(leftIndex + 1 < items.length && items[leftIndex + 1] > items[leftIndex]){//有右节点，并且右节点大于左节点时，替换成右节点
                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));
    }
}

具体的代码可以在源码中进行查看
个人博客