基本概念

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

在js中实现优先级队列

  1. // 因为我们每个元素都是一个对象，要包含本身的值，还有他的优先级，所以定义一个构造函数
  2. function QueueElement(item, priority) {
  3.   this._item = item;
  4.   this.priority = priority;
  5. }
  7. function PriorityQueue() {
  8.   this.items = [];
  9. }
  11. PriorityQueue.prototype.enqueue = function (element, priority) {
  12.   let queueElement = new QueueElement(element, priority);
  13.   if (this.items.length === 0) {
  14.     this.items.push(queueElement);
  15.   } else {
  16.     let flag = false;
  17.     for (let index = 0; index < this.items.length; index++) {
  18.       if (queueElement.priority < this.items[index].priority) {
  19.         this.items.splice(index, 0, queueElement);
  20.         flag = true;
  21.         break;
  22.       }
  23.     }
  24.     if (!flag) {
  25.       this.items.push(queueElement);
  26.     }
  27.   }
  28. };
  29. PriorityQueue.prototype.dequeue = function () {
  30.   return this.items.shift();
  31. };
  32. PriorityQueue.prototype.front = function () {
  33.   return this.items[0];
  34. };
  35. PriorityQueue.prototype.isEmpty = function () {
  36.   return this.items.length > 0 ? false : true;
  37. };
  38. PriorityQueue.prototype.size = function () {
  39.   return this.items.length;
  40. };
  41. PriorityQueue.prototype.toString = function () {
  42.   let str = "";
  43.   this.items.forEach(item => {
  44.     str = str + item.priority + "-" + item._item + " ";
  45.   });
  46.   return str;
  47. };
  49. const p1 = new PriorityQueue();
  50. p1.enqueue(5, 5);
  51. p1.enqueue(4, 4);
  52. p1.enqueue(3, 3);
  53. p1.enqueue(2, 2);
  54. p1.enqueue(1, 1);
  55. p1.enqueue(100, 100);
  57. p1.enqueue(0, 0);
  59. console.log(p1.toString());
  1. 我们在插入元素的时候需要指定当前元素的值还有他的优先级，所以我们生命一个构造函数。
  2. 然后分三种情况
    • 第一种情况，第一次插入的时候就没必要比较的，直接插入即可
    • 第二种情况，items里面有元素，我们需要根据当前元素的优先级来插入这个元素
    • 第三种情况，items元素遍历完了都没找到，说明他应该插入最后端，那么我们就直接push进去就完事了