Home 数据结构与算法 data structure

# 优先级队列结构

  • 优先级队列的特点

    • 我们知道，普通的队列插入一个元素，数据会被放在后端。并且需要前面所有的元素都处理完后才会处理前面的数据。
    • 但是优先级队列，再插入一个元素的时候会考虑该数据的优先级。和其他数据优先级 进行比较
    • 比较完成后，可以得出这个元素在队列中正确的位置
    • 其他处理方式，和基本队列的处理方式一样。

  • 优先级队列主要考虑的问题：

    • 每个元素不再只是一个数据，而且包含数据的优先级

# Example

  • 生活中的优先级队列例子
    • 比如某些家庭在吃饭时，老人优先级更高，先动筷子，其次是父母，最后才是小孩。
    • 你正在吃饭，突然非常想去五谷轮回之所，于是你就去了。

Example 1:

每次插入几组数据：
'Saber', 100
'Nekoaimer', 1000
'Lain', 10
输出：'Lain', 10  'Saber', 100  'Nekoaimer', 1000
  • 解释：第一个是为元素，第二个是为优先级。 那么这个例子我们就以认为数字越低 优先级越高来实现优先级队列 那么每次插入数据都会进行比较 排列，所以会得出这个结果。

Example 2:

每次插入几组数据：
'Saber', 1
'Nekoaimer', 3
'Lain', 2
输出：Saber 1  Lain 2  Nekoaimer 3

# Solving Ideas

// 封装优先级队列
function PriorityQueue() {
  // 1. 内部类
  function QueueElement(el, priority) {
    this.el = el
    this.priority = priority
  }
  // 封装属性
  this.items = []
  // 封装方法
  // 实现插入方法
  PriorityQueue.prototype.enqueue = function (el, priority) {
    // 1. 创建 QueueElement 对象
    const queueElement = new QueueElement(el ,priority)
    console.log(queueElement);
    // 3. 判断队列是否为空
    if (this.items.length === 0) {
      this.items.push(queueElement)
    } else {
      let added = false
      for (let i = 0; i < this.items.length; i++){
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement)
          added = true
          return;
        }
      }
      this.items.push(queueElement)
    }
  }
   // 4. 从队列中删除前端元素
   PriorityQueue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 5. 查看前端的元素
  PriorityQueue.prototype.front = function () {
    return this.items[0]
  }
  // 6. 查看队列是否为空
  PriorityQueue.prototype.isEmpty = function () {
    return this.items.length === 0
  }
  // 7. 查看队列中元素个数
  PriorityQueue.prototype.size = function () {
    return this.items.length
  }
  // 8.toString 方法
  PriorityQueue.prototype.toString = function () {
    let resStr = ''
    for (key of this.items) {
      resStr += key.el + ' ' + key.priority + '  '
    }
    return resStr
  }
}
// 测试代码
const pq = new PriorityQueue()
pq.enqueue('Lain', 10)
pq.enqueue('Saber', 100)
pq.enqueue('Nekoaimer', 1000)
console.log(pq)
/*
PriorityQueue {
  items: [
    QueueElement { el: 'Lain', priority: 10 },      
    QueueElement { el: 'Saber', priority: 100 },    
    QueueElement { el: 'Nekoaimer', priority: 1000 }
  ]
}
*/
console.log(pq.toString()) // Lain 10  Saber 100  Nekoaimer 1000