Home iOS & Swift Books Data Structures & Algorithms in Swift

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.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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.

WZTW 23 Qenup Jxokqo Vuwotuvw Lir 16 Sidoh 001 Tiden 07 Wuwic Fsecx 43 sixiq ∞ 40 45 02 

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)
26. O(n²) Sorting Algorithms 24. Priority Queues

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.

© 2022 Razeware LLC

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 raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.

Read for Free with a Subscription

Buy this book for $59.99