JavaScript 优先队列

在本教程中，我们将学习 JavaScript 中的优先队列数据结构。总的来说，优先队列是一种与队列或栈类似的数据结构。不同之处在于，每个元素都有一个“优先级”。在优先队列中，优先级更高的元素将首先被处理，而不是优先级较低的元素。如果优先级相同，则两个项目按它们在队列中的出现顺序排序。

优先队列是一种特殊的队列，它具有以下特定功能：

1. 优先队列中的每个元素都有特定的优先级。
2. 元素根据其优先级级别进行入队。
3. 优先级最低的元素最先出队。

实现优先队列主要有两种方法。一种是在队列末尾执行入队操作，然后根据优先级执行出队操作。另一种方法是根据优先级将元素放入队列，然后从队首取出。本文将重点介绍如何使用后一种方法实现优先队列。

注意：假设优先队列可以动态增长，我们不考虑溢出条件。

标准的 JavaScript 库不实现优先队列。但是，优先队列可以使用各种数据结构来实现，其中最常用的选项之一是二叉堆。

二叉堆

二叉堆是一种特殊设计的数据结构，它支持将 数组中的元素按偏好顺序排列。它看起来像一个数组，其中其值根据给定的键按升序（或降序）排列。优先级最高（或最低）的元素会更靠近数组的开头。以下结构使我们能够有效地检索和删除代表最高（或最低）优先级的元素。

类型

最小堆：最小堆的构造方式是，优先级较低的元素，即最小值，放在堆的顶部；这被称为根。由于这种安排，可以直接访问排队的最小值，并且最小堆的布局确保每个父节点的值都小于其子节点。

最大堆：最大堆定义为元素优先级最高，即最大值，位于顶部的堆。这种结构允许在出队时轻松访问最大元素。最大堆结构确保每个父节点的值大于其子节点，从而形成一个有利于快速检索最大元素的结构。最大堆结构保证每个父节点大于其子节点，从而形成一个可以轻松找到最大元素的分层结构。

实施

入队：将元素插入队列的过程。

语法

在此方法中，我们创建一个 qElement，它将具有一个元素属性和另一个优先级属性；然后，我们根据具有最高/最低优先级或最高优先级中最低的 qElement 应插入的实际位置来跟踪队列。

出队：从队列中提取元素的过程。

语法

这会从队列头部删除一个元素，因为最优先的元素必须位于优先队列的头部。在这里，数组的 shift 方法用于删除队列中的元素。

最小堆实现

入队：根据最低优先级将元素插入队列。

出队：从队列前端提取元素。

代码

输出

最大堆实现

入队：根据最高优先级将元素插入队列。

出队：从队列前端提取元素。

代码

输出

结论

JavaScript 不提供原生的优先队列；然而，这种基本实现对于需要有效排序的任务很有用。它可以根据特定要求修改为用作最小堆或最大堆，展示了 JavaScript 在各种编程环境中的多功能性。