Chapters

Hide chapters

Data Structures & Algorithms in Swift

Third Edition · iOS 13 · Swift 5.1 · Xcode 11

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

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 scrambled 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 the 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 provided 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 into 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 element 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.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now