引言

大家好啊，我是前端拿破轮😁。

最近学习算法题遇到了优先级队列的问题，遍想着写一篇文章来总结一下，好加深自己的印象。同时也希望能够帮助到有需要的各位同学。

老规矩，带着问题来读文章。

  1. 什么是优先级队列？
  2. 什么是大/小顶堆？
  3. 优先级队列和大/小顶堆是什么关系？
  4. 如何用TypeScript来实现一个优先级队列？
  5. 优先级队列有什么典型应用？
  6. 使用优先级队列要注意什么问题？

什么是优先级队列？

队列相信大家都清楚，就是一种先进先出(FIFO)的数据结构。而优先级队列是一种抽象数据结构，它类似于普通的队列，但是元素出队的顺序并不是先进先出，而是按优先级高低出队。

在优先级队列中，每次总是队列中优先级最高的元素先出队。至于什么是优先级高就取决于我们自己定义了。可能是数值越大，优先级越高，这就是大顶堆；也可能是数值越小，优先级越高，这就是小顶堆；还可能是其他判断条件。所以才说优先级队列是一种抽象的数据结构，具体规则需要我们去实现。

什么是大/小顶堆？

堆是一种完全二叉树结构，常用数组来实现。(因为二叉树既可以用数组存储，也可以用二叉链表来存储)。

堆主要有两种表现形式：

类型 定义 用途
小顶堆 父节点<=子节点(堆顶是最小值) 实现最小优先级队列
大顶堆 父节点>=子节点(堆定是最大值) 实现最大优先级队列

堆的常用操作push,pop,top的时间复杂度是O(logn)。

优先级队列和堆是什么关系？

正如前两点所说，优先级队列是一种抽象的数据结构，而堆则是将优先级这一指标具像化，通常是数值大小，从而实现为大顶堆或小顶堆。

可以说：堆是实现优先级队列最常见，较高效的方式。

如何用TypeScript来实现一个优先级队列