了解优先级队列

优先队列是一种特殊的队列,根据优先级插入和移除项目。在程序设计领域,优先队列的用途非常广泛。例如,我们有一个非常庞大的电子邮件队列系统,每月通过队列系统发送时事通讯。如果我们需要使用相同的队列功能向用户发送一封紧急邮件,该怎么办?由于队列的一般原则是将项目添加到最后,因此发送该邮件的过程将被大大延迟。为了解决这个问题,我们可以使用优先队列。在这种情况下,我们为每个节点分配一个优先级,并根据该优先级对它们进行排序。优先级较高的项目会排在列表的最前面,并且会更早被释放。

我们可以采用两种方法来建立优先级队列。

有序序列

如果我们为优先级队列规划一个有序序列,它可以有升序或降序。有序序列的积极意义在于,我们可以用 O(1) 的复杂度快速找到最大优先级项目或删除最大优先级项目。但插入将花费更多时间,因为我们必须检查队列中的每个元素,根据其优先级将项目放到正确的位置。

无序序列

无序序列不要求我们逐个队列元素来放置新添加的元素。作为一般队列原则,它总是被添加到后面。因此,我们可以用 O(1) 的复杂度实现 enqueue 操作。但是,如果我们要查找或删除优先级最高的元素,就必须逐个元素查找。因此,这对搜索并不友好。

现在,我们将编写代码,使用带链表的有序序列来实现优先级队列。