数据结构3-优先级队列

数据结构 Comments

优先级队列

优先级队列的优点

队列的有点是先进先出，这导致我们有的数据比较重要，却不能提前出来。优先级队列主要解决了这一痛点。

优先级实现

  1. 封装的元素要和优先级放在一起
  2. 添加元素的时候，要遍历优先级比较，进行存储

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
function PriorityQeueu(){
    // 创建一个对象，存储元素和优先级
    function Node(element,priority){
        this.element = element;
        this.priority = priority;
    }
    //数组存储对象
    var item = [];
    this.length = 0;
    // 数组是否为空
    this.isEmpty = function(){
        return this.length === 0;
    }
    // 添加元素
    this.enqueue = function(element,priority){
        var node = new Node(element,priority);
        // 如果数组是空的，那么就是第一个元素，直接加进来即可。
        if(this.isEmpty()){
            items.push(node);
        }else{
            //判断是否已经加入数组
            var added = false;
            // 遍历查询是否优先级比较高
            for(var i=0;i<this.length;i++){
                if(node.priority > item[i].priority){
                    //数字越高，优先级越高，进行插入
                    items.splice(i,0,node);
                    added = true;
                    break;
                }
            }
            // 如果都没有，说明数字是最小的，优先级是最低的，加在最后面。
            if(!added){
                items.push(node);
            }
        }
    }
    this.dequeue = function(){
        return items.shift();
    }
    
}


// 测试
pe = new PriorityqQueue()
pe.enqueue('a',1);
pe.enqueue('b',2);
pe.enqueue('c',3);
pe.enqueue('d',4);
alert(pe.dequeue().ele);
alert(pe.dequeue().ele);
alert(pe.dequeue().ele);
alert(pe.dequeue().ele);