优先级队列（Priority Queue）

队列一般都遵守着 先进先出(first-in-first-out )的顺序，优先级队列有点不同，它是按照优先级的顺序出队的，举个例子，一个优先级队列可能是：

• 1，最大优先级队列：在队列最前面的永远是优先级最高的。
• 2，最下优先级对垒：在队列最前面的永远是优先级最低的。

当需要在一组数据中找出最大值或者最小值时，使用优先级队列就非常的有用，在这篇文章中，你将体会到优先级队列的好处，我们借助于前面所学的queue和 heap数据结构来构建优先级队列。

公共的操作

queue 所遵守的 protocol 如下：

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

优先级队列和正常的队列有着共同的操作，只是在实现的方面有点不同。

实现

你可以通过以下几种方式去创建优先级队列。

• 1，Sorted array：在获取最大值和最小值的时候，效率非常高，复杂度为O(1),然而，由于在插入的时候需要按照顺序，导致插入操作非常慢，复杂度为O(n)
• 2 平衡二叉搜索树：在获取最大值和最小值的时候复杂为O(logn)，插入元素时，效率比 sortedArray高一些，为 O(logn)
• 3 堆(heap)：堆是构建优先级队列比较好的方式，在获取最大值和最小值的时候，复杂度为O(1),其他的操作复杂度都为O(logn)
  接下来，我们将使用堆来创建优先级队列。

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)
  }
}

• 1，优先级队列 遵守 Queue协议，泛型参数必须遵守 Equatable协议。
• 2，使用堆来实现优先级队列。
• 3，在构建方法中，使用sort函数来确定是最高优先级还是最低优先级队列。
  接下来，实现 Queue协议：

var isEmpty: Bool {
  return heap.isEmpty
}

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

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

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

• 1，在 enqueue(_:)方法中，往 heap中插入元素，会对元素进行 上滤操作，使堆符合其性质。整个 enqueue(_:)操作的复杂度为O(logn)。
• 2，在dequeue(_:)方法中，是通过将 堆中最后一个元素和根元素进行交换，然后对根节点执行 下滤实现的，整个出队操作的复杂度为O(logn)

最后附上本文的相关代码DataAndAlgorim

参考链接《Data Structures & Algorithms in Swift》