前面学习过队列这种数据结构，该数据结构的特点是先进先出，但有时候会出现特殊情况，比如在我们排队买票时，会有军人优先、老人优先等，当碰到军人买票时，得让他们优先购买，这就破坏了先进先出的结构，导致出现了另外一种数据结构，就是今天需要整理的优先队列。
概念
优先队列也称为堆，是指在队列中，具有优先级特性的元素，最先出队的元素。出队和入队的顺序无关，跟优先级相关。
优先队列表示方法
优先队列可以使用一种中做二叉树的结果来保存堆中的数据，被称作为二叉堆，二叉堆是一棵完全二叉树。所以我们可以使用数组来表示优先队列。对于数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在（2i+1）上，它的父新则在位置i/2上。以下是一个优先队列，并通过数组来表示它。
堆.jpeg
优先队代码实现
下面通过简单的代码来实现优先队列。
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));
}
}
