25.优先级队列的挑战

挑战1：基于数组的优先级队列

你已经学会了使用堆来构建一个符合Queue协议的优先级队列。现在，用一个Array构建一个优先级队列。

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

挑战2：优先选择等待名单

你最喜欢的T-Swift音乐会已经售罄。幸运的是，有一个候补名单，供仍然想去的人使用! 但是，门票销售首先会优先考虑有军事背景的人，其次是资历。写一个sort函数，按照提到的优先级返回等待名单上的人的名单。下面定义了Person结构：

public struct Person: Equatable {
  let name: String
  let age: Int
  let isMilitary: Bool
}

挑战3：尽量减少充电站

Swift-la是一家新的电动汽车公司，希望为他们的车辆增加一项新的功能。他们想为他们的客户增加检查汽车是否能到达指定目的地的能力。由于前往目的地的路程可能很远，所以有一些充电站，汽车可以在那里充电。该公司希望找到车辆到达目的地所需的minimum number of charging stops。

你会得到以下信息：

• 车辆需要行驶的target距离。
• startCharge，汽车有多少电量可以开始旅行。
• 一个有序的stations列表，汽车可能会在沿途停止充电。

每个ChargingStation都有一个离起始地点的distance和一个chargeCapacity。这个容量是一个站可以为汽车增加的充电量。

你可以假设如下：

1. 一辆电动汽车具有infinite的充电能力。
2. 一次充电量相当于一英里。
3. stations的列表是按与起始地点的距离排序的：

stations[0].distance < stations[1].distance < stations[k].distance

为了让你开始，我们提供了对象和函数。打开25-priorityqueue-challenge/projects/starter/PriorityQueueChallenge.playground并导航到Minimum Recharge Stops的playground页面。

解决方案

挑战1的解决方案

回顾一下，优先级队列是按优先顺序排队的。它可以是最小优先级队列，也可以是最大优先级队列。你已经得到了以下协议：

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

要制作一个基于数组的优先级队列，你所要做的就是符合Queue协议。你没有使用堆，而是使用一个数组数据结构!

首先，添加以下内容：

public struct PriorityQueueArray<T: Equatable>: Queue {

  private var elements: [T] = []
  let sort: (Element, Element) -> Bool

}

在PriorityQueueArray中，你存储一个元素数组和给定的sort函数。

sort函数帮助确定队列中元素的优先次序。

接下来添加以下初始化器：

public init(sort: @escaping (Element, Element) -> Bool,
            elements: [Element] = []) {
  self.sort = sort
  self.elements = elements
  self.elements.sort(by: sort)
}

初始化器需要一个sort函数和一个elements的数组。在init方法中，你利用了数组的sort函数。根据苹果的说法，排序函数需要O(n log n)时间。

Note

Swift的排序功能使用introsort，是插入排序和堆排序的结合。请看这里：https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift

接下来，你应该符合Queue协议。添加以下方法：

public var isEmpty: Bool {
  elements.isEmpty
}

public var peek: T? {
  elements.first
}

相当直截了当。要检查队列是否为空，检查数组是否为空。

要偷看队列的开始，返回数组的第一个元素。

接下来，添加enqueue方法：

public mutating func enqueue(_ element: T) -> Bool {
  for (index, otherElement) in elements.enumerated() { // 1
    if sort(element, otherElement) { // 2
      elements.insert(element, at: index) // 3
      return true
    }
  }
  elements.append(element) // 4
  return true
}

要将一个元素enqueue到基于数组的优先级队列中，请执行以下操作：

1. 对于队列中的每个元素。
2. 检查你要添加的元素是否有更高的优先级。
3. 如果有，在当前的 "索引 "处插入它。
4. 如果该元素的优先级不高于队列中的任何元素，则将该元素追加到最后。

这个方法总体上有O(n)的时间复杂度，因为你必须通过每个元素来检查你要添加的新元素的优先级。另外，如果你在数组中的元素之间插入，你必须将元素向右移动一个。

接下来添加dequeue方法：

public mutating func dequeue() -> T? {
  isEmpty ? nil : elements.removeFirst()
}

在这里，你在从数组中移除第一个元素之前，检查队列是否为空。这个方法是一个O(n)的操作，因为你必须将现有的元素向左移动一个。

最后，让我们以一种友好的格式打印出优先级队列。添加以下内容：

extension PriorityQueueArray: CustomStringConvertible {

  public var description: String {
    String(describing: elements)
  }
}

你有了! 一个基于数组的优先级队列!

为了测试优先级队列，添加以下内容：

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

挑战2的解决方案

你有以下Person的类型：

public struct Person: Equatable {
  let name: String
  let age: Int
  let isMilitary: Bool
}

给出一份等待名单上的人的名单，你想按以下顺序排列这些人的优先次序：

1. 军事背景
2. 资历，按年龄

解决这个问题的一个办法是使用一个优先级队列的数据结构，并建立一个适当的排序函数来解决优先级问题!

在下面添加以下排序函数：

func tswiftSort(person1: Person, person2: Person) -> Bool {
  if person1.isMilitary == person2.isMilitary {
    return person1.age > person2.age
  }

  return person1.isMilitary
}

tswiftSort取两个人，检查他们是否都有或没有军事背景。如果有，你就检查他们的年龄，如果没有，你就把优先权交给有军事背景的人。

为了测试你的优先排序功能，让我们通过添加以下内容尝试一个样本数据集：

let p1 = Person(name: "Josh", age: 21, isMilitary: true)
let p2 = Person(name: "Jake", age: 22, isMilitary: true)
let p3 = Person(name: "Clay", age: 28, isMilitary: false)
let p4 = Person(name: "Cindy", age: 28, isMilitary: false)
let p5 = Person(name: "Sabrina", age: 30, isMilitary: false)

let waitlist = [p1, p2, p3, p4, p5]

var priorityQueue = PriorityQueue(sort: tswiftSort, elements: waitlist)
while !priorityQueue.isEmpty {
  print(priorityQueue.dequeue()!)
}

挑战3的解决方案

该问题提供了两个实体让你开始。

第一个是ChargingStation：

struct ChargingStation {
  /// Distance from start location.
  let distance: Int
  /// The amount of electricity the station has to charge a car.
  /// 1 capacity = 1 mile
  let chargeCapacity: Int
}

第二个是DestinationResult：

enum DestinationResult {
  /// Able to reach your destination with the minimum number of stops.
  case reachable(rechargeStops: Int)
  /// Unable to reach your destination.
  case unreachable
}

DestinationResult描述了车辆是否能完成其旅程。

最后，该问题提供了一个minRechargeStops(_:)函数，有三个参数。

• target：车辆需要行驶的距离（英里）。
• startCharge: 开始旅程所需的起始电量。
• stations: 沿途的ChargingStation，按距离排序。

为了找到最小的充电站数量，一个解决方案是利用优先队列。

在minRechargeStops(_:)中添加以下内容：

func minRechargeStops(target: Int, startCharge: Int, stations: [ChargingStation]) -> DestinationResult {
  // 1
  guard startCharge <= target else {
    return .reachable(rechargeStops: 0)
  }

  // 2
  var minStops = -1
  // 3
  var currentCharge = 0
  // 4
  var currentStation = 0
  // 5
  var chargePriority = PriorityQueue(sort: >, elements: [startCharge])
}

查看初始设置：

1. 如果电动车的起始电量大于或等于目标目的地，那么它是.reachable的，没有任何停留。
2. minStops跟踪到达target所需的最小停车次数。
3. currentCharge跟踪车辆在旅程中的当前电量。
4. currentStation跟踪经过的站点数量。
5. chargePriority是一个优先级队列，保存所有可到达的充电站。它负责提供具有最高充电能力的站点。优先级队列也被初始化为车辆的startCharge。

接下来在minRechargeStops中添加以下内容：

// 1
while !chargePriority.isEmpty {
  // 2
  guard let charge = chargePriority.dequeue() else {
    return .unreachable
  }
  // 3
  currentCharge += charge
  // 4
  minStops += 1

  // 5
  if currentCharge >= target {
    return .reachable(rechargeStops: minStops)
  }

  // 6
  while currentStation < stations.count &&
        currentCharge >= stations[currentStation].distance {
    let distance = stations[currentStation].chargeCapacity
    _ = chargePriority.enqueue(distance)
    currentStation += 1
  }
}

// 7
return .unreachable

Recall

优先队列chargePriority将给我们提供具有最高充电能力的车站。

这个循环是一个贪婪的算法，因为优先级队列将始终给我们提供具有最高充电能力的可到达的车站，以便为车辆充电。

1. 如果chargePriority队列不是空的，这意味着有可到达的充电站，该车可以在那里充电。
2. chargePriority队列中移除充电能力最高的站。
3. 通过将charge加入到currentCharge中为车辆充电。
4. 每次从优先级队列中取消排队，必须增加minStops，因为你已经在一个车站停了下来。
5. 检查currentCharge是否能到达target。如果它能到达目标，返回.reachable和最小站数。
6. 我们当前的充电不能到达目的地，但是我们还没有用完所有的充电站，汽车的currentCharge可以到达下一个currentStation。让我们把该站的chargeCapacity添加到chargePriority队列中。
7. 我们无法到达目的地。

这就是了! 让我们为电动汽车公司Swift-la测试一下这个新功能吧!

let stations = [ChargingStation(distance: 10, chargeCapacity: 60),
                ChargingStation(distance: 20, chargeCapacity: 30),
                ChargingStation(distance: 30, chargeCapacity: 30),
                ChargingStation(distance: 60, chargeCapacity: 40)]

minRechargeStops(target: 100, startCharge: 10, stations: stations)

这个目标应该是可以达到的，至少有两站！