JS 优先队列

一般情况下从队列中删除的元素，一定是率先入队的元素。但是也有一些使用队列的应用，在删除元素时不必遵守先进先出的约定。这种应用，需要使用一个叫做优先队列（priority queue）的数据结构来进行模拟。

优先队列中元素的添加和移除是基于优先级的，从优先队列中删除元素时，需要考虑优先权的限制。优先队列具有最高级先出（First In Largest Out）的行为特征。

例如：医院急诊科（Emergency Department）的候诊室是采取优先队列的，当病人进入候诊室时，分诊护士会评估患者病情的严重程度，然后给一个优先级代码。高优先级的患者先于低优先级的患者就医，同样优先级的患者按照先来先服务的顺序就医。

function Patient(name,code){
    this.name = name;
    this.code = code;//整数表示患者的优先级或病情严重程度
}
function Queue(){
    this.data = [];
    /*入队*/
    this.enqueue = function(element){
        this.data.push(element);
    };
    /*出队：删除队列中更拥有最高优先级的元素，优先码最小的元素优先级最高。*/
    this.dequeue = function(){
        var priority = this.data[0].code;
        //使用顺序查找方法寻找优先级最高的元素，优先码越小优先级越高
        for(var i=0; i<this.data.length; ++i){
            if(this.data[i].code < priority){
                priority = i;
            }
        }
        return this.data.splice(priority,1);
    };
    this.toString = function(){
        var retstr = '';
        for(var i=0; i<this.data.length; ++i){
            retstr +=  this.data[i].name + " code: " + this.data[i].code + "\n";
        }
        return retstr;
    }
}

/*test*/
var queue = new Queue();
var p = new Patient('smith',5);
queue.enqueue(p);
p = new Patient('jones',4);
queue.enqueue(p);
p = new Patient('fehrenbach',6);
queue.enqueue(p);
p = new Patient('brown',1);
queue.enqueue(p);
p = new Patient('ingram',1);
queue.enqueue(p);
print(queue.toString());

var seen = queue.dequeue();
print(queue.toString());

实现优先队列有两种选项：

• 设置优先级然后再正确的位置添加元素
• 用入列操作添加元素然后按照优先级移除它们

function PriorityQueue(){
    var items = [];

    function QueueElement(element,priority){
        this.element = element;
        this.priority = priority;
    }

    this.enqueue = function(element, priority){
        var qe = new QueueElement(element, priority);
        //若队列为空则直接将元素入列否则需要比较该元素与其他元素的优先级
        if(this.isEmpty()){
            items.push(qe);
        }else{
            var added = false;
            //找出比要添加元素的优先级值更大的项目，就把新元素插入到它之前。
            for(var i=0; i<items.length; i++){
                //一旦找到priority值更大的元素就插入新元素并终止队列循环
                if(qe.priority < items[i].priority){
                    items.splice(i,0,qe);
                    added = true;
                    break;
                }
            }
            if(!added){
                items.push(qe);
            }
        }
    };

    this.isEmpty = function(){
        return items.length === 0;
    };
    this.print = function(){
        var str = '';
        for(var i=0; i<items.length; i++){
            str += items[i].priority + ' ' + items[i].element + '\n'
        }

        console.log(str.toString());
    }
}

这里实现的优先队列称为最小优先队列，因为优先级的值较小的元素被放置在队列最前面。最大优先队列则与之相反，把优先级的值较大的元素放置在队列最前面。

/*test*/
var pq = new PriorityQueue();
pq.enqueue('John',2);
pq.enqueue('Jack',1);
pq.enqueue('Camila',1);
pq.print();

最小优先队列