优先级队列（PriorityQueue）是个很有用的数据结构，很多编程语言都有实现。NodeJs是一个比较新潮的服务器语言，貌似还没有提供相关类。这些天有用到优先级队列，因为时间很充足，闲来无事，就自己实现了一下。代码如下：
/**
* script: pqueue.js
* description: 优先级队列类
* authors: alwu007@sina.cn
* date: 2016-04-19
*/ var util = require('util'); /**
* 优先级队列类
* @param cmp_func 优先级比较函数，必需，参考数组排序参数
*/
var PQueue = exports.PQueue = function(cmp_func) {
//记录数组
this._records = [];
//优先级比较方法
this._cmp_func = cmp_func;
}; //堆向上调整
PQueue.prototype._heapUpAdjust = function(index) {
var records = this._records;
var record = records[index];
var cmp_func = this._cmp_func;
while (index > 0) {
var parent_index = Math.floor((index - 1) / 2);
var parent_record = records[parent_index];
if (cmp_func(record, parent_record) < 0) {
records[index] = parent_record;
index = parent_index;
} else {
break;
}
}
records[index] = record;
}; //堆向下调整
PQueue.prototype._heapDownAdjust = function(index) {
var records = this._records;
var record = records[index];
var cmp_func = this._cmp_func;
var length = records.length;
var child_index = 2 * index + 1;
while (child_index < length) {
if (child_index + 1 < length && cmp_func(records[child_index], records[child_index + 1]) > 0) {
child_index ++;
}
var child_record = records[child_index];
if (cmp_func(record, child_record) > 0) {
records[index] = child_record;
index = child_index;
child_index = 2 * index + 1;
} else {
break;
}
}
records[index] = record;
}; //销毁
PQueue.prototype.destroy = function() {
this._records = null;
this._cmp_func = null;
}; //将记录插入队列
PQueue.prototype.enQueue = function(record) {
var records = this._records;
records.push(record);
this._heapUpAdjust(records.length - 1);
}; //删除并返回队头记录
PQueue.prototype.deQueue = function() {
var records = this._records;
if (!records.length)
return undefined;
var record = records[0];
if (records.length == 1) {
records.length = 0;
} else {
records[0] = records.pop();
this._heapDownAdjust(0);
}
return record;
}; //获取队头记录
PQueue.prototype.getHead = function() {
return this._records[0];
}; //获取队列长度
PQueue.prototype.getLength = function() {
return this._records.length;
}; //判断队列是否为空
PQueue.prototype.isEmpty = function() {
return this._records.length == 0;
}; //清空队列
PQueue.prototype.clear = function() {
this._records.length = 0;
};
我觉得，相对于其他排序算法而言，用堆实现优先级队列，入队时间波动较小，比较平稳。