Type at least 1 character to search
Back to top

The Priority Queue in Swift

The Priority Queue is a fundamental data structure.

The Priority Queue is a fundamental data structure, but one that is relatively new to the game.

Is it a data structure? Or is it just a way of looking at queues? and arrays?

In this entry, we’re using Priority Queues as a way to hold only the small number of max or min values from a streaming input.

It has a number of applications, including Huffman data compression and Dijkstra’s algorithm. So if you want to make a billion dollars by developing a new data compression method, you will want to understand the Priority Queue.

Imagine that you have a franchise of movie theaters with hundreds of transactions per day at each location and thousands of locations. And that you are interested in which theaters are doing the best business and which movies are doing the best. Sounds like a common use case, right?

Extend the example a bit: You are receiving the data in real time from each theater to your phone. On a given summer weekend evening you’re receiving a million transactions on every each quarter hour — shortly after the movies in your multiplexes start. And you are receiving all this data on your phone. It is being streamed to you as space-delimited data with each line containing the movie theater, the movie, the date and the dollar value of the gross receipts for that movie, and a carriage return at the end of each line.

Like this:

ohiocineplex14 Rocky2 4/12/2022 9:15 $500

indianacineplex23 Rocky3 4/12/2022 9:15 $900

Not only do you not want to store all the data, you can’t. If you store the data every night, you find that the memory allocation in your app gets filled and your app crashes. In any case, you don’t really want to see all the data. All you really want is the data from the movies that are bringing in the most money and you want to know the theaters that are doing the best.

So lets create a Priority Queue that keeps the income from the top 5 movies or the top 5 theater locations. Let us call the dictionary that holds the income from a specific movie at a specific location <MovieReceipts>.

With our Priority Queue, we want to find the largest k items in a stream of n items, where those items are of type <MovieReceipts>.

To do this, the general concept is to create a Priority Queue where we can delete the minimum. Once we have this, we can read the data stream, and add incoming items to the Priority Queue. If the number of items in the Priority Queue exceeds k, then we delete the minimum item.

Consider the elementary implementations first.  In this implementation, we’ll create a Priority Queue as an array. And when the number of entries in the Priority Queue exceeds the max, we will iterate through the array to remove the minimum. Most of the code is parsing the lines.

First, here’s a list of results. Copy these to a text file called movieReceipts.txt and move it to the home folder.

ohiocineplex14 Rocky 4/12/2022 $1400

ohiocineplex14 Rocky2 4/12/2022 $1500

ohiocineplex14 Rocky3 4/12/2022 $200

ohiocineplex14 Rocky4 4/12/2022 $16000

ohiocineplex14 Rocky 4/12/2022 $1300

ohiocineplex14 Rocky2 4/12/2022 $14500

ohiocineplex14 Rocky3 4/12/2022 $2050

ohiocineplex14 Rocky4 4/12/2022 $160300

ohiocineplex14 Rocky 4/12/2022 $140

ohiocineplex14 Rocky2 4/12/2022 $500

ohiocineplex14 Rocky3 4/12/2022 $900

ohiocineplex14 Rocky4 4/12/2022 $1000

ohiocineplex14 Rocky 4/12/2022 $144500

ohiocineplex14 Rocky2 4/12/2022 $150

ohiocineplex14 Rocky3 4/12/2022 $20

ohiocineplex14 Rocky4 4/12/2022 $1600

Then create a Mac console app like we’ve done before. The first func we’ll add — ‘runPriorityQueue()’ — will read in the file and parse the lines one by one. It’s not a real streaming input, but since we’re parsing the lines one at a time, it will behave like one:

public func runPriorityQueue() {

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

            addToPriorityQueue(movieReceipt: line)


    } catch {

        assertionFailure(“Failed reading from URL: (maybeFile), Error: ” + error.localizedDescription)


    print(“final PQ = (unorderedPriorityQueue)”)


This function will parse the lines and then add them one at a time to the Priority Queue — unorderedPriorityQueue


var unorderedPriorityQueue = [String]()

let priorityQueueMaxSize = 6

// Add a new value to the Priority Queue and delete the minimum if the size of the Priority Queue exceeds the max:

public func addToPriorityQueue(movieReceipt: String) {


    if unorderedPriorityQueue.count > priorityQueueMaxSize {




After we exceed the priorityQueueMaxSize, we’ll call the code that deletes the minimum value:

// Find the minimum value in the Priority Queue and delete it:

public func deleteMin() {

    var minIndex: Int = 0

    for (index, _) in unorderedPriorityQueue.enumerated() {

        if compare(s1: unorderedPriorityQueue[index], s2: unorderedPriorityQueue[minIndex]) {

            minIndex = index



    unorderedPriorityQueue = exchangeWithEnd(a1: unorderedPriorityQueue, s1: minIndex)

    unorderedPriorityQueue.remove(at: unorderedPriorityQueue.count – 1)


public func exchangeWithEnd(a1: [String], s1: Int) -> [String] {

    var a = a1

    let temp = a[s1]

    a[s1] = a[a.count – 1]

    a[a.count – 1] = temp

    return a


// Compare two income values:

public func compare(s1: String, s2: String) -> Bool {

    return getValue(s: s1) < getValue(s: s2)


// Parse the income Float value:

public 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

    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


And that’s it. You can run this by calling runPriorityQueue() from the main.swift file, and then enter the file name ‘movieReceipts.txt’ in the console below the prompt.

Please enter the name of a file in your home directory:

We’ve not discussed any applications yet. But you can already start to imagine how you might process the adjacent pixel values from an image while running a compression algorithm — put the adjacent values in a priority queue, process them and move on. Next time we’ll get into more complex — and faster — variations.


James Robinson Douglas Stewart