优先级队列

基本概念

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。还是那句话，维基百科喜欢用概念解释概念，简而言之：正常的队列，插入一个元素，都会放到后端，优先级队列需要在插入元素的时候考虑这个数据的优先级，然后和别的元素比较优先级，最后得出这个元素在队列中正确的位置。

在js中实现优先级队列

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
55
56
57
58
59
// 因为我们每个元素都是一个对象，要包含本身的值，还有他的优先级，所以定义一个构造函数
function QueueElement(item, priority) {
  this._item = item;
  this.priority = priority;
}

function PriorityQueue() {
  this.items = [];
}

PriorityQueue.prototype.enqueue = function (element, priority) {
  let queueElement = new QueueElement(element, priority);
  if (this.items.length === 0) {
    this.items.push(queueElement);
  } else {
    let flag = false;
    for (let index = 0; index < this.items.length; index++) {
      if (queueElement.priority < this.items[index].priority) {
        this.items.splice(index, 0, queueElement);
        flag = true;
        break;
      }
    }
    if (!flag) {
      this.items.push(queueElement);
    }
  }
};
PriorityQueue.prototype.dequeue = function () {
  return this.items.shift();
};
PriorityQueue.prototype.front = function () {
  return this.items[0];
};
PriorityQueue.prototype.isEmpty = function () {
  return this.items.length > 0 ? false : true;
};
PriorityQueue.prototype.size = function () {
  return this.items.length;
};
PriorityQueue.prototype.toString = function () {
  let str = "";
  this.items.forEach(item => {
    str = str + item.priority + "-" + item._item + " ";
  });
  return str;
};

const p1 = new PriorityQueue();
p1.enqueue(5, 5);
p1.enqueue(4, 4);
p1.enqueue(3, 3);
p1.enqueue(2, 2);
p1.enqueue(1, 1);
p1.enqueue(100, 100);

p1.enqueue(0, 0);

console.log(p1.toString());
  1. 我们在插入元素的时候需要指定当前元素的值还有他的优先级，所以我们生命一个构造函数。
  2. 然后分三种情况
    • 第一种情况，第一次插入的时候就没必要比较的，直接插入即可
    • 第二种情况，items里面有元素，我们需要根据当前元素的优先级来插入这个元素
    • 第三种情况，items元素遍历完了都没找到，说明他应该插入最后端，那么我们就直接push进去就完事了