The Priority Queue in Swift III.
Priority Queues with Binary Heaps in Swift. 2: Swimming Up and Sinking Down the Tree.
Last time we ended with a description of how we can add a value to the end of a Priority Queue and then swim ‘up’ the tree until we reach the proper position in the tree. Here’s a visualization. Imagine that we somehow end up with a node value of 72 below a node with a value of 68. We must resolve this inconsistency. We do it by swimming up the tree and exchanging the node with a value of 72 with the parent node whose value is 68:
The result of this exchange is shown here:
But the node with a value of 72 is still out of place: It’s parent node is smaller. So we must repeat the exchange as indicated. And the result is here:
Now we finally have the node whose value is 72 in the correct place. We did this by swimming up the tree. The code to swim up is here:
private func swim<T: Comparable>(_ arr: [T], _ i: Int) -> [T] {
var k = i
var a = arr
while k >= 1 && (a[k/2] < a[k]) {
a = exchange(a, i: k, j: k/2)
k = k/2
}
return a
}
Notice in the above ‘swim’ function that, first, we are using a generic value ‘T’ to represent the item at the node. And whatever this item is, it must conform to ‘Comparable.’
Second, notice that we aren’t swimming up a tree. Rather, we are swimming up an array. We are swimming up the array representation of the tree as described last time.
In the array representation, if a node is at index ‘k’, then its parent node is at index ‘k/2.’
Thus in the ‘while’ loop, we are comparing the value of our node at ‘k’ to the value of the parent node at ‘k/2.’ And as long as the parent is smaller than the child, we exchange the parent and the child. That’s how we swim up the tree/array.
Today we’ll add a new ‘Movie Receipt’ object to our Priority Queue. This object must be comparable. Here’s the code to represent this object:
import Foundation
public class MovieReceipt: Comparable {
public static func == (lhs: MovieReceipt, rhs: MovieReceipt) -> Bool {
getValue(s: lhs.receipt) == getValue(s: rhs.receipt)
}
public static func < (lhs: MovieReceipt, rhs: MovieReceipt) -> Bool {
getValue(s: lhs.receipt) < getValue(s: rhs.receipt)
}
var receipt: String
init(receipt: String) {
self.receipt = receipt
}
// Parse the income Float value:
static func getValue(s: String) -> Float {
var lowerIndex = s.firstIndex(of: “$”) ?? s.startIndex
lowerIndex = s.index(after: lowerIndex)
let upperIndex = s.firstIndex(of: “n”) ?? s.endIndex
// movieReceipts.txt
var str: String
if upperIndex == s.endIndex {
str = String(s[lowerIndex..<upperIndex])
} else {
str = String(s[lowerIndex..<upperIndex])
}
let val = Float(str) ?? 0.0
return val
}
}
extension MovieReceipt: CustomStringConvertible {
public var description: String {
return self.receipt + “n”
}
}
Notice that the MovieReceipt object has a variable called ‘receipt’ that is the string representation of the object.
Last time we just used the string. This time we are placing the code to parse the dollar value of the string in the new MovieReceipt object.
Also in a change from last time, today we’ll create a Priority Queue that only saves the minimum movie receipts. Imagine that the manager is a good person — they want to focus on the theaters and movies that need help. So they’re looking for the lowest income values. Here’s the rest of the code to insert a new value into the Priority Queue.
In brief: First, we add a value to the end of the array of MovieReceipts.
Second, we swim that value up the array (tree) until it reaches the correct position where it’s not smaller than its children and it’s not greater than its parents.
Third, if we’ve exceeded the proper size of the priority queue, then we delete the current max value.
That’s it! That’s a complete representation of the Priority Queue in Swift.
Add this to a console app. And in the main class, run it by adding: runPQ()
//
// SwimAndSink
// PriorityQueues
//
// Fastest App
// Copyright © 2024 Datascream, Inc. All rights reserved
//
// Swift 5.0
//
import Foundation
var PQ = [MovieReceipt]()
let maxPQSize = 6
public func insert<T: Comparable>(x: T) where T: MovieReceipt {
if PQ.count == 0 {
PQ.append(MovieReceipt.init(receipt: “”))
}
PQ.append(x)
PQ = swim(PQ, PQ.count – 1)
if PQ.count > maxPQSize {
PQ = deleteMaximum(PQ)
}
}
private func swim<T: Comparable>(_ arr: [T], _ i: Int) -> [T] {
var k = i
var a = arr
while k > 1 && (a[k/2] < a[k]) {
a = exchange(a, i: k, j: k/2)
k = k/2
}
return a
}
private func sink<T: Comparable>(_ arr: [T], _ i: Int) -> [T] {
var a = arr
var k = i
let n = a.count – 1
while 2*k < n {
var j = 2*k
if j < n && a[j] < a[j+1] {
j += 1
}
if a[k] >= a[j] {
break
}
a = exchange(a, i: k, j: j)
k = j
}
return a
}
public func deleteMaximum<T: Comparable>(_ arr: [T]) -> [T] {
var a = arr
let n = a.count – 1
a = exchange(a, i: 1, j:n)
a.remove(at: n)
a = sink(a, 1)
return a
}
public func deleteMinimum<T: Comparable>(_ arr: [T]) -> [T] {
var a = arr
let n = a.count – 1
a.remove(at: n)
return a
}
public func deleteMin2() {
var minIndex: Int = 0
for (index, _) in PQ.enumerated() {
if PQ[index] < PQ[minIndex] {
minIndex = index
}
}
PQ = exchangeWithEnd(a1: PQ, s1: minIndex)
PQ.remove(at: PQ.count – 1)
}
public func exchange<T: Comparable>(_ arr: [T], i: Int, j: Int) -> [T] {
var a = arr
let temp = a[i]
a[i] = a[j]
a[j] = temp
return a
}
public func runPQ() {
// Input the path
print(“Please enter the name of a file in your home directory:”)
let filePath = readLine() ?? “”
let home = FileManager.default.homeDirectoryForCurrentUser
let maybeFile = home.appendingPathComponent(filePath)
let fileManager = FileManager.default
do {
let contents = try fileManager.contentsOfDirectory(atPath: home.path)
let urls = contents.map { home.appendingPathComponent($0) }
if urls.contains(maybeFile) {
print(“found the file”)
}
} catch {
print(“couldn’t find file”)
}
var inString = “”
do {
inString = try String(contentsOf: maybeFile)
let s = String(inString)
// read in the lines one by one:
var lowerIndexInt = 0
var upperIndexInt = s.count
var lowerIndex = s.startIndex
var upperIndex = s.endIndex
let end = String.Index(utf16Offset: upperIndexInt, in: s)
var done: Bool = false
while !done {
// Create a substring to the first n
let start = String.Index(utf16Offset: lowerIndexInt, in: s)
let substring = String(s[start..<end])
lowerIndex = substring.startIndex
upperIndex = substring.firstIndex(of: “n”) ?? substring.endIndex
var line: String
if upperIndex == substring.endIndex {
line = substring
done = true
} else {
line = String(substring[lowerIndex…upperIndex])
lowerIndexInt = lowerIndexInt + (upperIndex.utf16Offset(in: substring) + 1)
}
// Add that substring to the Priority Queue
if upperIndex.utf16Offset(in: substring) – lowerIndex.utf16Offset(in: substring) > 1 {
var movieReceipt = MovieReceipt(receipt: line)
if PQ.count == 0 {
}
insert(x: movieReceipt)
} else {
print(“Error”)
}
}
} catch {
assertionFailure(“Failed reading from URL: (maybeFile), Error: ” + error.localizedDescription)
}
print(“final PQ = (PQ)”)
}