25. Priority Queue Challenges

Written by Vincent Ngo

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.

You’re given the following information:

• The target distance the vehicle needs to travel.
• The startCharge, how much charge the car has to begin the journey.
• An ordered list of stations that the car can potentially stop at to charge along the way.

Each ChargingStation has a distance from the start location and a chargeCapacity. This is the amount of charge a station can add to the car.

You may assume the following:

1. An electric car has an infinite charge capacity.
2. One charge capacity is equivalent to one mile.
3. The list of stations is sorted by distance from the start location:

stations[0].distance < stations[1].distance < stations[k].distance

To get you started, objects and functions are provided. Open 25-priorityqueue-challenge/projects/starter/PriorityQueueChallenge.playground and navigate to Minimum Recharge Stops playground page.

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 }
}

To make an array based priority queue, all you have to do is conform to the Queue protocol. Instead of using a heap, you use an array data structure!

First add the following:

public struct PriorityQueueArray<T: Equatable>: Queue {

  private var elements: [T] = []
  let sort: (Element, Element) -> Bool

}

Within the PriorityQueueArray you store an array of elements, and the given sort function.

The sort function helps prioritize the elements in the queue.

Next add the following initializer:

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

The initializer takes a sort function, and an array of elements. Within the init method, you leverage the array’s sort function. Accord to Apple the sort function takes O(n log n) time.

Swift’s sort function uses introsort which is a combination of insertion sort and heap sort. Check it out here: https://github.com/apple/swift/blob/master/stdlib/public/core/Sort.swift

Next you should conform to the Queue protocol. Add the following methods:

public var isEmpty: Bool {
  elements.isEmpty
}

public var peek: T? {
  elements.first
}

Fairly straightforward. To check if the queue is empty, simply check if the array is empty.

To peek at what’s at the start of the queue, simply return the first element of the array.

Next, add the enqueue method:

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
}

To enqueue an element into an array-based priority queue do the following:

1. For every element in the queue.
2. Check to see if the element you are adding has a higher priority.
3. If it does, insert it at the current index.
4. If the element does not have a higher priority than any element in the queue, simply append the element to the end.

This has overall O(n) time complexity, since you have to go through every element to check the priority against the new element you are adding. Also if you are inserting in between elements in the array, you have to shift elements to the right by one.

Next add the dequeue method:

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

Here you simply check to see if the queue is empty before removing the first element from the array. This is an O(n) operation, since you have to shift the existing elements to the left by one.

Finally let’s print out the priority queue in a nice format. Add the following:

extension PriorityQueueArray: CustomStringConvertible {

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

There you have it! An array-based priority queue!

To test out the priority queue add the following:

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
}

Given a list of people on the waitlist, you would like to prioritize the people in the following order:

1. Military background
2. Seniority, by age

One solution to this problem is using a priority queue data structure, and build a proper sort function to address the priority!

Add the following sort function below:

func tswiftSort(person1: Person, person2: Person) -> Bool {
  if person1.isMilitary == person2.isMilitary {
    return person1.age > person2.age
  }

  return person1.isMilitary
}

tswiftSort takes two people and checks to see if both of them have or don’t have a military background. If so, you check their age, if not, you give priority to whoever has a military background.

To test your priority sort function out, let’s try a sample data set by adding the following:

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:

The first is 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
}

The second is 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 describes whether it is possible for the vehicle to complete its journey.

Lastly the question provides a minRechargeStops(_:) function with three parameters.

• target: the distance in miles the vehicle needs to travel.
• startCharge: the starting charge you have to start the journey.
• stations: the ChargingStations along the way, sorted by distance.

In order to find the minimum number of charging stations to stop at, one solution is to leverage a priority queue.

Add the following in 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])
}

Going over the initial setup:

1. If the starting charge of the electric vehicle is greater than or equal to the target destination, it is .reachable with zero stops.
2. minStops keeps track of the minimum number of stops needed to reach target.
3. currentCharge keeps track of the vehicle’s current charge on the journey.
4. currentStation tracks the number of stations passed.
5. chargePriority is a priority queue that holds all the reachable charging stations. It is responsible for providing the station with the highest charging capacity. The priority queue is also initialized with the vehicle’s startCharge.

Next add the following to minRechargeStops:

// 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

Recall: The priority queue chargePriority will give us the station with the highest charge capacity.

This is a greedy algorithm in that the priority queue will always give us the reachable station with the highest capacity to charge the vehicle.

1. If the chargePriority queue is not empty, this means that there are reachable charging stations the car can charge at.
2. chargePriority queue removes the station with the highest charge capacity.
3. Charge the vehicle by adding the charge to currentCharge.
4. Every time you dequeue from the priority queue, you must increment minStops, since you’ve stopped at a station.
5. Check to see if the currentCharge can reach the target. If it can reach the target, simply return .reachable with the minimum stops.
6. Our current charge can’t reach our destination but we have not exhausted all charging stations, and the car’s currentCharge can reach the next currentStation. Let’s add the station’s chargeCapacity to the chargePriority queue.
7. We are unable to reach the destination.

That’s it! Let’s test this new feature out for electric car company Swift-la!

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)

This should be reachable with two minimum stops!