第24章：优先级队列

队列是简单的列表，使用先进先出（FIFO）排序来维持元素的顺序。优先级队列是队列的另一个版本，其中元素按照优先级顺序排队，而不是使用先进先出排序。例如，一个优先级队列可以是。

1. 最大优先级，在这种情况下，前面的元素总是最大的。

2. 最小优先级，在这个队列中，前面的元素总是最小的。

当确定一个元素列表的最大值或最小值时，优先级队列特别有用。在本章中，你将了解优先级队列的好处，并利用你在前几章学习的现有队列和堆数据结构来建立一个优先级队列。

应用

优先级队列的一些实际应用包括。

• Dijkstra算法，该算法使用优先级队列来计算最小成本。

• A*寻路算法，该算法使用优先级队列来跟踪未开发的路线，从而产生长度最短的路径。

• 堆排序，可以用优先级队列来实现。

• 哈夫曼编码，它建立了一个压缩树。一个最小优先级队列被用来反复寻找两个频率最小的、还没有父节点的节点。

这些只是一些用例，但优先级队列也有很多应用。

常见操作

在第8章队列中，你为队列建立了以下协议。

一个优先级队列的操作与普通队列相同，所以只有实现方式不同。

优先级队列将符合队列协议并实现常见的操作。

• enqueue。向队列中插入一个元素。如果操作成功则返回true。

• dequeue: 移除具有最高优先级的元素并将其返回。如果队列是空的，则返回nil。

• isEmpty。检查队列是否为空。

• peek: 返回具有最高优先级的元素，而不删除它。如果队列是空的，则返回nil。

让我们看一下实现优先级队列的不同方法。

实现方式

你可以通过以下方式创建一个优先级队列。

1. 排序的数组。这对于在O(1)时间内获得一个元素的最大值或最小值很有用。然而，插入的速度很慢，需要O(n)，因为你必须按顺序插入。

2. 平衡的二进制搜索树。这在创建双端优先级队列时很有用，其特点是在O(log n)时间内同时获得最小值和最大值。插入比排序的数组好，也是在O(log n)。

3. 堆。这是优先级队列的一个自然选择。堆比排序数组更有效，因为堆只需要部分排序。所有的堆操作都是O(log n)，除了从一个最小优先级的堆中提取最小值是一个快如闪电的O(1)。同样，从最大优先级的堆中提取最大值也是O(1)。

接下来，你将看看如何使用堆来创建一个优先级队列。打开启动器playground来开始吧。在Source文件夹中，你会注意到以下文件。

1. Heap.swift。你将使用堆数据结构（来自前一章）来实现优先级队列。

2. Queue.swift。包含定义队列的协议。

在主playground页面中，添加以下内容。

struct PriorityQueue<Element: Equatable>: Queue { 
  // 1 
  private var heap: Heap<Element> // 2 
  
  init(sort: @escaping (Element, Element) -> Bool, 
    heap = Heap(sort: sort, elements: elements) 
  }
  // more to come ...
}

我们来看看这个代码。

1. PriorityQueue将符合Queue协议。通用参数Element必须符合Equatable，因为你需要比较元素。

2. 你将使用这个堆来实现优先级队列。

3. 通过向这个初始化器传递一个适当的函数，PriorityQueue可以用来创建最小和最大优先级队列。

为了符合队列协议，请在init(sort:elements:)初始化器的后面添加以下内容。

堆是优先级队列的完美候选者。你需要调用堆的各种方法来实现优先级队列的操作!

1. 从上一章中，你应该明白，通过调用enqueue(:)，你插入到堆中，而堆会向上筛选以验证自己。enqueue(:)的总体复杂度是O(log n)。

2. 通过调用dequeue(_:)，你将根元素从堆中移除，用堆中的最后一个元素代替，然后向下筛选验证堆。dequeue()的总体复杂度是O(log n) 。

测试

在你的playground上添加以下内容。

你会注意到，优先级队列与普通队列有相同的接口。前面的代码创建了一个最大优先级队列。注意到元素从大到小被移除。下面的数字会被打印到控制台。

12
8
7
6
4
3
1
1

关键点

• 优先级队列经常被用来按优先级顺序查找元素。

• 它通过专注于队列的关键操作而撇开堆数据结构所提供的额外功能，创建了一个抽象层。

• 这使得优先级队列的意图清晰而简明。它唯一的工作就是对元素进行排队和取消排队，除此之外别无他法。

• 组成的胜利!

---

上一章	目录	下一章