ノードJsを使って優先順位の列PQueを実現します.

優先順位の行列はとても役に立つデータ構造で、多くのプログラミング言語が実現されます.NodeJsは比較的新しいサーバー言語で、まだ関連の種類を提供していないようです.ここ数日は優先順位の列があります.時間が十分あるので、暇な時は大丈夫です.自分で実現します.コードは以下の通りです

/**
 * script: pqueue.js
 * description:       
 * authors: [email protected]
 * 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;
};

 他の並べ替えアルゴリズムに比べて、優先キューをスタックで実現すると、入隊時間の変動が少なく、比較的安定していると思います.