第25章：优先级队列进阶

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

您已经学会了使用堆来构建符合队列协议的优先级队列。现在，用一个数组构造一个优先级队列。

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音乐会已经售罄。幸运的是，对于仍然想去的人来说，有一份候补名单! 但是，门票销售首先会优先考虑有军事背景的人，其次是资历。编写一个排序函数，按所述优先级返回等待名单上的人的名单。Person结构定义如下。

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

挑战3：尽量减少充电站

Swift-la是一家新的电动汽车公司，希望为他们的车辆增加一个新的功能。他们希望为客户增加检查汽车是否能到达指定目的地的功能。由于到达目的地的路程可能很远，所以有一些充电站，汽车可以在那里充电。该公司希望找到汽车到达目的地所需的最小充电站数量。

你会得到以下信息。

车辆需要行驶的目标距离。
startCharge，汽车有多少电量可以开始旅程。
一个有序的充电站列表，汽车可能会在沿途停下来充电。

每个充电站都有一个与起始地点的距离和一个充电容量。这个容量是一个充电站可以为汽车增加的电量。你可以假设以下情况。

一辆电动汽车有无限的充电能力。
一个充电容量相当于一英里。
车站的列表是按照与起始地点的距离排序的。

为了让你开始工作，我们提供了对象和函数。打开25-priorityqueuechallenge/projects/starter/PriorityQueueChallenge.playground，导航到最小充电站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中，你存储一个元素数组和给定的排序函数。

这个排序函数有助于对队列中的元素进行优先排序。

接下来添加以下初始化程序。

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

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

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

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

public var isEmpty: Bool { 
  elements.isEmpty 
}

public var peek: T? { 
  elements.first 
}

相当直截了当。要检查队列是否为空，检查数组是否为空。要偷看队列的起始部分，返回数组的第一个元素。接下来，添加enqueue方法。

要将一个元素排入基于数组的优先级队列，请执行以下操作。

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

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

接下来添加dequeue方法。

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

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

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

extension PriorityQueueArray: CustomStringConvertible {

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

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

为了测试这个优先级队列，请添加以下内容。

挑战2的解决方案

你得到了以下的人的类型。

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

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

军事背景
资历，按年龄

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

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

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

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

挑战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(_:)函数，有三个参数。

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

为了找到最少要停靠的充电站，一个解决方案是利用优先级队列。

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

查看初始设置。

如果电动车的起始电量大于或等于目标目的地，那么它是可以通过零停留到达的。
minStops跟踪到达目标地所需的最小停车次数。
currentCharge跟踪车辆在旅途中的当前电量。
currentStation跟踪所经过的站点数量。
chargePriority是一个优先级队列，持有所有可到达的充电站。它负责提供具有最高充电能力的站点。优先级队列也是用车辆的startCharge初始化的。

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

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

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

如果chargePriority队列不是空的，这意味着有可到达的充电站，汽车可以在那里充电。
chargePriority队列会移除具有最高充电能力的站。
给汽车充电，把充电量加到currentCharge中。
每次从优先级队列中取消排队时，必须增加minStops，因为你已经在一个站台上停了下来。
5.检查currentCharge是否能到达目标。如果它能到达目标，返回.可到达的最小站点。
我们当前的电量不能到达目的地，但是我们还没有用完所有的充电站，汽车的currentCharge可以到达下一个currentStation。让我们把该站的chargeCapacity添加到chargePriority队列中。
我们无法到达目的地。

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

这个目标应该是可以通过两个最小的站点来实现的!

上一章	目录	下一章