25.
Priority Queue Challenges
Written by Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Challenge 1: Array-based priority queue
You have learned to use a heap to construct a priority queue by conforming to the Queue protocol. Now, construct a priority queue using an Array.
public protocol Queue {
associatedtype Element
mutating func enqueue(_ element: Element) -> Bool
mutating func dequeue() -> Element?
var isEmpty: Bool { get }
var peek: Element? { get }
}
Challenge 2: Prioritize a waitlist
Your favorite T-Swift concert was sold out. Fortunately, there is a waitlist for people who still want to go! However, ticket sales will first prioritize someone with a military background, followed by seniority. Write a sort function that will return the list of people on the waitlist by the priority mentioned. The Person struct is defined below:
public struct Person: Equatable {
let name: String
let age: Int
let isMilitary: Bool
}
Challenge 3: Minimize recharge stops
Swift-la is a new electric car company that is looking to add a new feature to their vehicles. They want to add the ability for their customers to check if the car can reach a given destination. Since the journey to the destination may be far, there are charging stations that the car can recharge at. The company wants to find the minimum number of charging stops needed for the vehicle to reach its destination.
stations[0].distance < stations[1].distance < stations[k].distance
Solutions
Solution to Challenge 1
Recall that a priority queue dequeues elements in priority order. It could either be a min or max priority queue. You have been given the following protocol:
public protocol Queue {
associatedtype Element
mutating func enqueue(_ element: Element) -> Bool
mutating func dequeue() -> Element?
var isEmpty: Bool { get }
var peek: Element? { get }
}
public struct PriorityQueueArray<T: Equatable>: Queue {
private var elements: [T] = []
let sort: (Element, Element) -> Bool
}
public init(sort: @escaping (Element, Element) -> Bool,
elements: [Element] = []) {
self.sort = sort
self.elements = elements
self.elements.sort(by: sort)
}
public var isEmpty: Bool {
elements.isEmpty
}
public var peek: T? {
elements.first
}
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
}
public mutating func dequeue() -> T? {
isEmpty ? nil : elements.removeFirst()
}
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()!)
}
Solution to Challenge 2
You are given the following Person type:
public struct Person: Equatable {
let name: String
let age: Int
let isMilitary: Bool
}
func tswiftSort(person1: Person, person2: Person) -> Bool {
if person1.isMilitary == person2.isMilitary {
return person1.age > person2.age
}
return person1.isMilitary
}
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()!)
}
Solution to Challenge 3
The question provides two entities to get you started:
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
}
enum DestinationResult {
/// Able to reach your destination with the minimum number of stops.
case reachable(rechargeStops: Int)
/// Unable to reach your destination.
case unreachable
}
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
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
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)