1. 介绍
优先队列就是在我们插入一个元素的同时，赋予它一个优先级。相比于普通的队列，优先队列在有更广泛的用途。
比如在系统资源调度上，主程序就要比辅程序有更高的优先级，不然当内存不够用时，主程序可能就会面临被杀死以释放内存的风险。在现实生活中，优先队列的思想也被广泛应用，比如在公交车上，一般老弱病残就拥有较高的优先级。
讲完了概念，下面就来看看怎么去实现优先队列。
2. 简单实现
所谓简单实现，也就是说我们采用顺序插入的方式去实现优先队列。当插入一个元素的时候，我们所要做的工作基本如下：
-
检查当前队列是否为空，如果为空直接插入数组，否则进行下一步。
-
从头到尾比较新插入元素与队列中各元素的优先级，直到找到一个比新插入元素优先级更小的，将新元素插入到当前位置，如果没找到，则进行下一步。
-
如果到了第三步，说明当前队列非空而且队列中的元素优先级都高于新插入元素，这个时候我们将新元素插入到队列末尾即可。
了解了基本思想，下面就来看一下代码 ：
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);
}
}
};
可见，实现一个优先队列的确很简单，不过上面这种简单的实现，好像算法的效率并不高，因为 splice() 方法的效率并不高，关于 splice() 方法实现原理，你可以参考 splice方法实现原理分析 一文。
既然如此，我们可能想到了，一般涉及到大量插入和删除的时候，我们会选择链表，这的确是一个好的选择，下面我们就来看看用链表来实现优先队列。
3. 基于链表的优先队列
为了使用链表来保存对象，首先我们需要自定义一个 Node 类。
function Node(element, priority) {
this.element = element;
this.priority = priority;
this.next = null;
}
当然，你也可以将这个队列定义成双向指针，这样操作起来可能更容易理解一些。不过为了方便，我使用了单向的链表。
基本思想和上面的一样，下面我们看一下具体实现代码。
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++;
};
当一个元素入队时，首先的步骤主要如下：
-
如果当前链表为空，则直接将头结点指向插入元素即可。
-
如果插入的节点优先级比头结点还要高，那么直接将要插入元素的
next指针指向头指针，然后将头指针直接赋值。 -
如果上述两种情况都不符合，那就开始逐个遍历元素，如果找到了比要插入元素优先级低的已入队元素，那就将要插入的元素放下来，这个时候只需要改变两次指针指向即可。
-
值得注意的是，我们需要判断要插入元素如果需要放置在尾节点，那么将不得不进行
current.next === null的判断。
让我们来比较以下利用链表与不用链表的差别在哪里，插入元素时，不使用链表和使用链表都需要经过 N 次比较，但是如果移动元素的话，那么使用链表的时间复杂度为 O(1), 不使用链表的话则为 O(N) 。
虽然使用链表已经使优先队列得到了优化，不过这还远远不够，一般如果我们想到优化性能时，都会情不自禁的想到树，因为对于一个用于 N 个节点的二叉树而言，仅有 lgN 层，这样的话就有可能让我们的算法性能大幅度提升。下面我们就用堆这中数据结构来实现优先队列。
4. 堆结构的优先队列
当一颗二叉树的每个节点都大于或小于它的两个子节点的时候，它被称之为堆。
当根节点的值大于它的两个子节点的时候，称之为大根堆，反之成为小根堆。
一般用完全二叉树表达堆，因为它有一些易于我们编程的性质。
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
我们可以用数组来存储完全二叉树，不过一般我们从数组下标为 1 开始使用，因为这样的话，就可以轻松的算出一个根节点的两个子节点被放置在哪个位置。比如对于第 1 个元素，它的左子节点的坐标就是 (2 * 1), 它的右子节点的坐标就是 (2 * 1 + 1)。
为了完成功能，我首先写了两个辅助函数，less() 用于比较优先级，exch 用于交换两个元素的位置。
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;
};
下面就来介绍两个核心的函数，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);
}
};
当我们在数组中插入一个新的元素时，一般将元素插入到数组末尾，然后调用 swim() 将元素上浮到其应在的位置，这个函数的执行步骤如下：
-
当前下标如果小于等于 1， 则直接退出函数，因为这时元素已经在第一的位置，记住我们是从下标 1 开始存入元素的。
-
如果当前位置的元素大于其父元素，则交换位置，并重置下标继续执行循环语句。
swim() 函数总能保证一个刚插入的元素找到它的最终位置。不过值得注意的是在 JavaScript 中我们不得不利用 Math.floor() 确保每次运算得到的下标都是一个整数。
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;
}
};
当我们删除了一个元素之后，我们需要在删除节点的子节点中找到一个去顶替它，sink() 函数就是为了保证我们在删除元素的时候整个堆仍然是有序的，其工作步骤主要如下：
当下标为 k 的元素仍有子节点时， 寻找其左右子节点中优先级高的那一个，如果较高的那一个比 k 的优先级高，则交换位置，否则直接跳出循环。
好了，两个核心的函数介绍完毕了，下面来看看如果在队列中插入元素的方法。
this.enqueue = function(element, priority) {
var item = new Item(element, priority);
items[++length] = item;
swim(length);
};
值得提醒的是，由于在完全二叉树中并没有要求左子树和右字数之间的大小需要满足什么关系，所以你在打印结果的时候看到的并不是一个有序的集合。不过能够保证的是你每次弹出的元素其优先级一定是最高的。
this.dequeue = function() {
var max = items[1];
exch(1, length--);
items[length + 1] = null;
sink(1);
return max;
};
在弹出队列时，我们将最后一个元素与第一个优先级最高的元素进行交换，然后重新调用 sink() 恢复堆的有序性。
你可以在 我的 Github 查看源码～
网友评论