前言

博主最近在准备面试，刷了很多算法题，将近350道了。

把一些题单也过了，比如LeetCode 热题 100 和 面试常见150题。这些题单里的题目基本上都是面试中非常高频出现的，涵盖的知识面也非常的广：

• 动态规划
• 哈希表
• 回溯、记忆化搜索、深度、广度优先搜索
• 图、图的遍历、邻接表、邻接矩阵
• 单调栈
• 贪心
• 数学
• 前缀、后缀和
• 字典树
• 0-1背包问题
• 滑动窗口
• 二叉树、二叉平衡树、二叉搜索树、二叉树的遍历
• 分治、归并排序、二分查找
• 优先队列、大顶堆、小顶堆
• 等等等等.....

刷完这些题的时候，自然会明白自己擅长哪方面，不擅长哪方面。比如博主本人，比较擅长滑动窗口、单调栈、图论、dfs、二叉树等，比较不擅长动态规划、贪心、分治、优先队列等等。

遇到自己不擅长的题目，真的很想逃避呢，刷题的挫败感也是满满，啊，真不想去看题解啊

但是逃避解决不了任何问题，其他方面都已经很努力了，要是因为这里伏笔了导致满盘皆输，就太亏了。

套用《under tale》里的著名格式：

“你鼓起勇气克服自己的弱点，这使你充满了决心。”

于是本着能够 向外输出知识 就代表 对内彻底消化知识 的主旨，这篇关于“优先队列”的博客就诞生了！

希望能通过这篇博客，和大家一起，彻底掌握优先队列这个数据结构（啃下这块硬骨头），并能够自己写出js或者ts版本的“板子代码”，让我们后续再遇到相关的算法题时，能够迎刃而解。

行文思路

由于和博主之前写的博客都不同，因此特地在这里提一下本文的结构。我还是会采用 WWH 的方式去和大家一起学习优先队列:

• What ：优先队列是什么
• Why ：为什么使用优先队列
• How ：优先队列是怎么实现的

What

优先队列是什么？

优先队列比我们熟知的队列（queue）多了2个字，“优先”。

望文生义的话，我们不难想到优先队列应该是一种比较特殊的队列。

那我们先回顾一下队列（queue）和栈（stack）。

（本文不做任何详细的对比，因为这两种数据结构深入人心。）

队列和栈最广为人知的区别就是元素的插入和删除操作（即 入队、出队、入栈、出栈）。

• 队列：元素操作遵循FIFO(first in, first out)原则，最早插入队列中的元素，最早被删除。

• 栈：元素操作遵循LIFO(last in, first out)原则，最早插入栈中的元素，最晚被删除。

  

我们顺着“元素的插入和删除操作”这个角度去思考，那么所谓的优先队列，和队列的区别是不是也在这方面上呢？

没错，正是如此。

优先队列是一种特殊类型的队列，其中每个元素都有一个与之相关的优先级。在优先队列中，元素的出队顺序是基于其优先级而不是FIFO(first in, first out)顺序。具体来说，优先级高的元素会先出队，而优先级相同的元素则按照它们在队列中的顺序依次出队。

Why

为什么使用优先队列

在上一小节，我们提到了优先队列中的元素处理操作是遵循优先级的，而不是简单地按照元素的入队顺序。这样的设计具备非常广泛的应用场景，比如：

1. 任务调度：在操作系统中，优先队列常用于管理进程和线程，确保优先级高的任务先被执行。

2. 网络路由：在网络数据包的路由选择中，优先队列可以用来管理不同类型的数据流，确保重要数据优先传输。

3. 数据压缩：在霍夫曼编码等数据压缩算法中，优先队列用于构建最优的编码树。

4. 算法实现：

   • 图算法：例如Dijkstra算法和A*搜索算法中，优先队列用于选择下一个要处理的节点。
   • 最小生成树算法：如Prim算法，使用优先队列来选择最小权重的边

How

优先队列是怎么实现的

当我们在力扣去根据🏷标签搜索算法题的时候，可以看到👇优先队列和堆绑定在了一起👇：

堆是一种实现优先队列的方式。而根据堆的定义，堆必须是一棵完全二叉树，并且满足堆序性。

堆

完全二叉树

一棵能够被称之为【完全二叉树】的二叉树需要满足下方的3个条件：

1. 所有层都是满的，除了最后一层：完全二叉树除了最后一层外，每一层都被严格地填满，即每一层的节点数都达到最大值。
2. 最后一层的节点都集中在左侧：在完全二叉树中，最后一层的节点从左到右连续排列。
3. 最后一层的节点之间不存在空位：这意味着如果倒数第二层的某个节点存在右子节点，那么它必须也有左子节点。展开来说，完全二叉树的任何一个节点都不能只有右子节点而没有左子节点。

符合【完全二叉树】定义的二叉树✔

不符合【完全二叉树】定义的二叉树❌

堆序性

堆序性是指堆中的某个节点值，总是不大于或不小于其父节点的值。

我们可以根据堆序性，将堆分为2类：

• 大顶堆：每个父节点的值均大于子节点

  

• 小顶堆：每个父节点的值均小于子节点

了解完堆的2个性质之后，我们是不是就可以把堆和优先队列联系起来了呢？

👇我们来看这样的一个大顶堆👇：

如果把节点的值看成是优先级，大顶堆中最先被删除（被执行）的元素（任务）是不是就是堆顶元素了？这就正好符合优先队列中关于元素出队的原则了（优先级最高的任务最先被执行）。

那么接下来就是如何确保任务能够按照 10、8、7、5、3、2、1 的顺序被正确执行了，即当堆顶元素出去之后，如何才能让8成为下一个堆顶元素呢？

同理，当有优先级更高的任务进入堆中时，堆又该如何能够让新的任务成为堆顶元素呢？

基本操作

在上一章节的内容中，我们学习了有关【堆序性】的内容，并在掌握内容之后，能够理解为什么堆会和优先队列联系起来了。

但是上一章节也遗留了一个问题：

堆是如何完成对【堆序性】的维护工作，从而确保堆顶元素至始至终都是最大或最小的呢？

这就不得不提到堆的基本操作了：上浮（shift up）和下沉（shift down）。

上浮↑

当有新的节点（任务）进入堆（优先队列）时，堆会进行 上浮 操作。新节点首先会被插入至末尾，即完全二叉树的最后一层的最后一个叶节点后面，或者是满二叉树的新的一层的第一个节点（以大顶堆为例）。

之后，新节点会与其父节点进行值的比较，如果其值大于父节点，则将新节点与其父节点交换。

与父节点的比较行为会一直持续，直到无法再继续上移（确实小于父节点了或者当前比较的已经是堆顶元素）。

可以看到，经过 上浮 操作之后，【堆序性】被满足，所有的父节点都大于其子节点。

下沉↓

当堆顶元素（任务）离开堆（被执行）时，堆将进行 下沉 操作。堆首先会将当前堆中的末尾元素移动至堆顶。

而后开始执行堆顶元素与其子节点的比较，堆顶元素若小于其子节点，则会与子节点中较大的那一个交换。

这种父节点与子节点的值比较行为也将一直持续，直到无法再继续下移（父节点确实大于它的全部子节点了，或者已经移动至底部）。

可以看到，经过 下沉 操作之后，【堆序性】被满足，所有的父节点都大于其子节点，新的堆顶元素是当前堆中最大的。

存储结构

在上一章节的内容里，我们了解了堆的基本操作，明白了当发生节点的新增或删除时，堆是如何完成维护工作，从而确保其【堆序性】的。

理论知识我们已经学得差不多了，接下来就要准备动手写代码了。既然要写代码，我们就得明白，这样的一个大顶堆，它是以什么样的形式被存储的？继而才能根据其存储结构，去写具体的基本操作代码，使得我们的 MyPriorityQueue 能够实现 上浮 和 下沉 的操作。

我们结合实际例子来讨论堆的存储结构，如下图：

上图这样的一个大顶堆，它是以什么样的形式被存储的呢？

我们先对这棵【完全二叉树】进行层序遍历（从上到下，从左至右），完成编号。

编号完毕后，我们可以创建一个size为7的数组，将堆中的节点按照编号-索引值的规则依次填入数组中。

正是因为堆是一棵【完全二叉树】，才能够使得数组中的索引值能够和树中的每个节点一一对应。

于是，我们便可以使用一个一维数组 [10, 7, 8, 5, 3, 2, 1] 来表示一个堆。

是不是还缺了点什么？

举个例子，我们如何以一个一维数组去完成 上浮 和 下沉 操作呢？

比如把 [10, 7, 8, 5, 3, 2, 1] 变成 [8, 7, 2, 5, 3, 1]

是的，这个疑问一针见血，一维数组是扁平结构，如何去构建父子关系呢？毕竟 上浮 和 下沉 操作实际上依赖于父子节点之间的比较。

巧了，由于堆是一棵【完全二叉树】，因此节点的索引值与节点的父子关系存在简单的数学关系：

• 对于任意节点 i（假设数组的起始索引为 0 ）：

  • 它的左子节点的索引是 2i + 1
  • 它的右子节点的索引是 2i + 2
  • 它的父节点的索引是 Math.floor((i - 1) / 2)

我们拿节点8 来验证一下这个数学关系是否正确。

• 节点8，它的索引值是 2：

  • 它的左子节点的索引是 2*2 + 1 = 5，即节点2 ✔

  

  • 它的右子节点的索引是 2*2 + 2 = 6，即节点1 ✔

  

  • 它的父节点的索引是 Math.floor((2 - 1) / 2) = 0，即节点10 ✔

验证完毕，数学关系正确✔。

代码时间💻

在前面的内容里，我们讨论了堆的存储结构，可以用一维数组表示一个堆，并且节点间的父子关系正好也可以使用数学关系表示。

接下来，就是敲代码环节了，我会写2个版本的代码，js和ts。其中，js版本会和大家一起，一步一步完成整体代码的编写。

而ts版本，就当作是留给各位有幸点进此文章的掘友们的练习题了~

js

js版本会使用ES6引入的class关键字，完成MyPriorityQueue的编写。

当我们去写MyPriorityQueue，我们首先要明确我们最终的实现效果。我们可以先列出一部分伪代码，表示MyPriorityQueue能够做到的事情。

const myPQ = new MyPriorityQueue();

// 入队
myPQ.insert(10)
// 出队
myPQ.shift()
// 得到堆顶元素，即优先队列的队首元素
myPQ.top
// 得到当前队列的大小
myPQ.size
// 当前队列
console.log("heap", myPQ.heap);

明确这些基本功能后，我们来动手写一些。

以实现一个大顶堆为例，首先写好大致的基础结构。

class MyPriorityQueue {
  constructor() {
    this.heap = [];
  }

  get size() {
    return this.heap.length;
  }
  get top() {
    if (this.size !== 0) {
      return this.heap[0];
    } else {
      return null;
    }
  }

  insert(num) {}

  shift() {
    // 只有堆不为空时，才会出队
    if (this.size !== 0) {
      this.heap.shift();
    }
  }
}

我们可以把判断堆是否为空也写成一个get方法，避免重复多次出现this.size !== 0

class MyPriorityQueue {
  constructor() {
    this.heap = [];
  }

  get size() {
    return this.heap.length;
  }
  get isEmpty() {
    return this.size === 0;
  }
  get top() {
    if (!this.isEmpty) {
      return this.heap[0];
    } else {
      return null;
    }
  }

  insert(num) {}

  shift() {
    // 只有堆不为空时，才会出队
    if (!this.isEmpty) {
      this.heap.shift();
    }
  }
}

然后，我们知道，当堆中元素发生变化时，堆要完成相应的 上浮 和 下沉的操作，因此我们还需要写2个方法，shiftUp 和 shiftDown，并且，这两个方法我们期望只在MyPriorityQueue.insert和MyPriorityQueue.shift中内部调用，而不能在外部让用户主动调用，因此我们可以给这两个方法前面再加上#符号。

class MyPriorityQueue {
  constructor() {
    this.heap = [];
  }

  get size() {
    return this.heap.length;
  }
  get isEmpty() {
    return this.size === 0;
  }
  get top() {
    if (!this.isEmpty) {
      return this.heap[0];
    } else {
      return null;
    }
  }

  insert(num) {
    this.#shiftUp();
  }

  shift() {
    // 只有堆不为空时，才会出队
    if (!this.isEmpty) {
      this.heap.shift();
      this.#shiftDown();
    }
  }

  #shiftUp() {
    console.log("上浮");
  }

  #shiftDown() {
    console.log("下沉");
  }
}

这样，当用户试图在外部调用时，编译器会报错提示

好的，到此为止，模板已经搭建完毕，接下来就要完成几个函数方法内部的逻辑编写了。

先来写#shiftUp()，根据我们之前的分析，上浮 操作通常发生在堆中插入新的节点时。因此它应该放在MyPriorityQueue.insert内部调用。

而对于insert()方法，我们接收一个节点值作为参数，并将此节点值插入至堆的末尾节点。

  insert(num) {
    // 使用push方法，在数组末尾加入新的节点
    this.heap.push(num);
    // 而后开始【上浮】操作
    this.#shiftUp();
  }

而后调用#shiftUp()方法，使得堆从末尾节点开始，不断让其和父节点进行比较，直到无法继续上浮。

  #shiftUp() {
    console.log("上浮");
    // 获得当前插入节点的索引值
    let currentIndex = this.size - 1;

    // 上浮是个循环的行为，直到节点无法再继续上浮
    // 即 成为堆顶元素
    while (currentIndex > 0) {
      // 根据数学关系，获取到父节点的索引值
      let parentIndex = Math.floor((currentIndex - 1) / 2);

      // 如果当前节点的值 大于 父节点
      if (this.heap[currentIndex] > this.heap[parentIndex]) {
        // 通过解构赋值完成值的交换
        [this.heap[currentIndex], this.heap[parentIndex]] = [
          this.heap[parentIndex],
          this.heap[currentIndex],
        ];

        // 当前节点的索引值也同样替换为父节点
        currentIndex = parentIndex;
      }

      // 上浮是个循环的行为，直到节点无法再继续上浮
      // 即 确实小于父节点
      else {
        break;
      }
    }
  }

让我们用一个测试用例试试，我们写的上浮函数是否能够保证堆的【堆序性】

• 输入： [1, 2, 3, 5, 7, 8, 10]

• 期望输出： 符合大顶堆的一维数组

const testNums = [1, 2, 3, 5, 7, 8, 10];

for (const num of testNums) {
  myPQ.insert(num);
}
// 当前队列
console.log("heap", myPQ.heap);

运行之后的结果

我们再通过可视化工具，看下[10, 5, 8, 1, 3, 2, 7]转换成完全二叉树的样子：

可以看到，所有的父节点均大于子节点，满足大顶堆的【堆序性】！

接下来我们再写下沉的逻辑，下沉 操作通常发生在删除堆顶节点时。因此它应该放在MyPriorityQueue.shift内部调用。

 
   shift() {
    // 只有堆不为空时，才会出队
    if (!this.isEmpty) {
      // 由于我们要将末尾元素移动至堆顶
      // 因此我们可以先交换末尾元素和堆顶元素
      // 然后再执行pop方法，将堆顶元素移除
      const lastIndex = this.size - 1;
      // 同样使用解构赋值完成交换
      [this.heap[lastIndex], this.heap[0]] = [
        this.heap[0],
        this.heap[lastIndex],
      ];
      // 删除堆顶元素
      const topValue = this.heap.pop();
      // 执行 下沉 操作
      this.#shiftDown();

      return topValue;
    }
  }

而后调用#shiftDown()方法，使得堆从堆顶节点开始，不断让其和子节点进行比较，直到无法继续下沉。

 
 #shiftDown() {
    console.log("下沉");
    // 获得当前插入节点的索引值
    let currentIndex = 0;

    // 下沉是个循环的行为，直到节点无法再继续下沉
    // 即 移动至底部
    while (currentIndex * 2 + 1 < this.size) {
      // 根据数学关系，获取到子节点的索引值
      let leftChildIndex = 2 * currentIndex + 1;
      let rightChildIndex = 2 * currentIndex + 2;
      // 获取较大子节点的索引值
      let compareChildIndex =
        this.heap[leftChildIndex] > this.heap[rightChildIndex]
          ? leftChildIndex
          : rightChildIndex;

      // 如果当前节点的值 小于 子节点
      if (
        this.heap[currentIndex] <
        Math.max(this.heap[leftChildIndex], this.heap[rightChildIndex])
      ) {
        // 通过解构赋值完成值的交换
        [this.heap[currentIndex], this.heap[compareChildIndex]] = [
          this.heap[compareChildIndex],
          this.heap[currentIndex],
        ];

        // 当前节点的索引值也同样替换为子节点
        currentIndex = compareChildIndex;
      }

      // 下沉是个循环的行为，直到节点无法再继续下移
      // 即 确实大于子节点
      else {
        break;
      }
    }
  }

同样的，我们使用一个测试用例来测试我们写的函数是否正确

• 输入： 刚刚维护好的大顶堆[10, 5, 8, 1, 3, 2, 7]
• 输出： 每次移除堆顶元素后，剩余的堆符合【堆序性】

// 当前队列
console.log("heap", myPQ.heap);
// [10, 5, 8, 1, 3, 2, 7];
const count = myPQ.size;
for (let i = 0; i < count; i++) {
  const removeValue = myPQ.shift();
  console.log("被移除的堆顶元素", removeValue);
  console.log("当前堆", myPQ.heap);
}

执行后的结果：

同样的，我们利用可视化工具，展示下每次下沉后的堆是否符合【堆序性】

可以看到，所有的父节点均大于子节点，满足大顶堆的【堆序性】！

至此，我们成功实现了自己的优先队列！！！

完整代码

class MyPriorityQueue {
  constructor() {
    this.heap = [];
  }

  get size() {
    return this.heap.length;
  }
  get isEmpty() {
    return this.size === 0;
  }
  get top() {
    if (!this.isEmpty) {
      return this.heap[0];
    } else {
      return null;
    }
  }

  insert(num) {
    this.heap.push(num);
    this.#shiftUp();
  }

  shift() {
    // 只有堆不为空时，才会出队
    if (!this.isEmpty) {
      // 由于我们要将末尾元素移动至堆顶
      // 因此我们可以先交换末尾元素和堆顶元素
      // 然后再执行pop方法，将堆顶元素移除
      const lastIndex = this.size - 1;
      // 同样使用解构赋值完成交换
      [this.heap[lastIndex], this.heap[0]] = [
        this.heap[0],
        this.heap[lastIndex],
      ];
      // 删除堆顶元素
      const topValue = this.heap.pop();
      // 执行 下沉 操作
      this.#shiftDown();

      return topValue;
    }
  }

  #shiftUp() {
    console.log("上浮");
    // 获得当前插入节点的索引值
    let currentIndex = this.size - 1;

    // 上浮是个循环的行为，直到节点无法再继续上浮
    // 即 成为堆顶元素
    while (currentIndex > 0) {
      // 根据数学关系，获取到父节点的索引值
      let parentIndex = Math.floor((currentIndex - 1) / 2);

      // 如果当前节点的值 大于 父节点
      if (this.heap[currentIndex] > this.heap[parentIndex]) {
        // 通过解构赋值完成值的交换
        [this.heap[currentIndex], this.heap[parentIndex]] = [
          this.heap[parentIndex],
          this.heap[currentIndex],
        ];

        // 当前节点的索引值也同样替换为父节点

        currentIndex = parentIndex;
      }

      // 上浮是个循环的行为，直到节点无法再继续上浮
      // 即 确实小于父节点
      else {
        break;
      }
    }
  }

  #shiftDown() {
    console.log("下沉");
    // 获得当前插入节点的索引值
    let currentIndex = 0;

    // 下沉是个循环的行为，直到节点无法再继续下沉
    // 即 移动至底部
    while (currentIndex * 2 + 1 < this.size) {
      // 根据数学关系，获取到子节点的索引值
      let leftChildIndex = 2 * currentIndex + 1;
      let rightChildIndex = 2 * currentIndex + 2;
      // 获取较大子节点的索引值
      let compareChildIndex =
        this.heap[leftChildIndex] > this.heap[rightChildIndex]
          ? leftChildIndex
          : rightChildIndex;

      // 如果当前节点的值 小于 子节点
      if (
        this.heap[currentIndex] <
        Math.max(this.heap[leftChildIndex], this.heap[rightChildIndex])
      ) {
        // 通过解构赋值完成值的交换
        [this.heap[currentIndex], this.heap[compareChildIndex]] = [
          this.heap[compareChildIndex],
          this.heap[currentIndex],
        ];

        // 当前节点的索引值也同样替换为子节点
        currentIndex = compareChildIndex;
      }

      // 下沉是个循环的行为，直到节点无法再继续下移
      // 即 确实大于子节点
      else {
        break;
      }
    }
  }
}

测试用例

const myPQ = new MyPriorityQueue();

// 入队
myPQ.insert(10);
// 出队
myPQ.shift();

// myPQ.#shiftUp();
console.log(myPQ.isEmpty);

// 得到堆顶元素，即优先队列的队首元素
console.log(myPQ.top);
// 得到当前队列的大小
console.log(myPQ.size);

const testNums = [1, 2, 3, 5, 7, 8, 10];

for (const num of testNums) {
  myPQ.insert(num);
}
// 当前队列
console.log("heap", myPQ.heap);
// [10, 5, 8, 1, 3, 2, 7];
const count = myPQ.size;
for (let i = 0; i < count; i++) {
  const removeValue = myPQ.shift();
  console.log("被移除的堆顶元素", removeValue);
  console.log("当前堆", myPQ.heap);
}

ts

期待你的答案：

    //write something.... 

题单

阅读完本文，你是否也能够手写一个优先队列了呢？

👇那么趁热打铁，试试下面的题单吧👇：

• 215. 数组中的第K个最大元素 - 力扣（LeetCode）
• 373. 查找和最小的 K 对数字 - 力扣（LeetCode）
• 295. 数据流的中位数 - 力扣（LeetCode）
• 502. IPO - 力扣（LeetCode）