跳转至

24.优先级队列

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

  1. Max-priority，在这种情况下，排在前面的元素总是最大的。
  2. Min-priority，排在前面的元素总是最小的。

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

应用

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

  • Dijkstra’s algorithm，它使用优先级队列来计算最小成本。
  • A pathfinding algorithm，该算法使用优先级队列来跟踪未开发的路线，以产生长度最短的路径。
  • `Heap sort，可以使用优先级队列实现。
  • Huffman coding，建立一个压缩树。一个最小优先级队列被用来反复寻找两个频率最小的、还没有父节点的节点。

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

常见操作

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

public protocol Queue {
  associatedtype Element
  mutating func enqueue(_ element: Element) -> Bool
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var peek: Element? { get }
}

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

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

  • enqueue：向队列中插入一个元素。如果操作成功，返回true。
  • dequeue：移除具有最高优先级的元素并返回。如果队列是空的，则返回nil。
  • isEmpty：检查队列是否为空。
  • peek：返回具有最高优先级的元素，而不删除它。如果队列是空的，则返回nil。

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

实施

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

  1. Sorted array：这对于在O(1)时间内获得一个元素的最大值或最小值很有用。但是，插入的速度很慢，需要O(n)，因为你必须按顺序插入。
  2. Balanced binary search tree：这在创建双端优先级队列时很有用，其特点是在O(log n)时间内同时获得最小值和最大值。插入比排序的数组更好，也是在O(log n)。
  3. Heap：这是优先级队列的一个自然选择。堆比排序数组更有效，因为堆只需要部分排序。所有的堆操作都是O(log n)，除了从一个最小优先级的堆中提取最小值是一个快如闪电的O(1)。同样，从一个最大优先级的堆中提取最大值也是O(1)。

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

  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,
       elements: [Element] = []) { // 3
    heap = Heap(sort: sort, elements: elements)
  }

  // more to come ...
}

我们来看看这个代码：

  1. PriorityQueue将符合Queue协议。通用参数Element必须符合Equatable，因为你需要比较元素。
  2. 你将使用这个堆来实现优先级队列。
  3. 通过向这个初始化器传递一个适当的函数，PriorityQueue可以用来创建最小和最大的优先级队列。

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

var isEmpty: Bool {
  heap.isEmpty
}

var peek: Element? {
  heap.peek()
}

mutating func enqueue(_ element: Element) -> Bool { // 1
  heap.insert(element)
  return true
}

mutating func dequeue() -> Element? { // 2
  heap.remove()
}

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

  1. 从上一章中，你应该明白，通过调用enqueue(_:)，你插入到堆中，而堆会向上筛选以验证自己。enqueue(_:)的总体复杂性是O(log n)。
  2. 通过调用dequeue(_:)，你从堆中移除根元素，将其替换为堆中的最后一个元素，然后向下筛查验证堆。dequeue()的总体复杂度是O(log n)。

测试

在你的Playground上添加以下内容：

var priorityQueue = PriorityQueue(sort: >, elements: [1,12,3,4,1,6,8,7])
while !priorityQueue.isEmpty {
  print(priorityQueue.dequeue()!)
}

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

12
8
7
6
4
3
1
1

关键点

  • 优先级队列经常被用来寻找priority order中的元素。
  • 它通过专注于queue的关键操作来创建一个抽象层，而忽略了由堆数据结构提供的额外功能。
  • 这使得优先级队列的意图清晰而简明。它唯一的工作是enqueue和dequeue元素，其他的都不需要!
  • 胜利的组合!