## Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 6 chapters

# 25. Priority Queue Challenges Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

### 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)
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.