Implementing a Priority Queue Fast AF

As a developer, you may have come across situations where you need to prioritize certain tasks or elements over others. One way to handle this is through the use of a priority queue. A priority queue is a data structure that allows you to store elements and assign them a priority level, with the highest priority elements being processed first.

In this tutorial, we will explore multiple ways to implement a priority queue in Swift and how they work.

Using a sorted array

One way to implement a priority queue is through the use of a sorted array. To do this, we will create a struct called PriorityQueue with a generic Element type. We will also create a property called elements which will be an array of tuples, with each tuple containing an element and its priority level.

struct PriorityQueue<Element> {
    var elements: [(element: Element, priority: Int)] = []
}

Next, we will implement the basic operations for a priority queue: enqueue, dequeue, and peek.

For the enqueue operation, we will simply append the element and its priority level to the elements array and then sort the array based on the priority level.

extension PriorityQueue {
    mutating func enqueue(_ element: Element, withPriority priority: Int) {
        elements.append((element, priority))
        elements.sort { $0.priority < $1.priority }
    }
}

For the dequeue operation, we will remove the first element in the array, which will be the highest priority element due to the sorting.

extension PriorityQueue {
    mutating func dequeue() -> Element? {
        guard !elements.isEmpty else { return nil }
        return elements.removeFirst().element
    }
}

For the peek operation, we will simply return the first element in the array.

extension PriorityQueue {
    func peek() -> Element? {
        return elements.first?.element
    }
}

Now we have a basic implementation of a priority queue using a sorted array.

Using a heap

Another way to implement a priority queue is through the use of a heap. A heap is a complete binary tree where the parent node is always greater than or equal to its children (for a max-heap) or less than or equal to its children (for a min-heap). This ensures that the highest or lowest value is always at the root of the tree.

To implement a priority queue using a heap, we will create a struct called HeapPriorityQueue with a generic Element type. We will also create a property called elements which will be an array of tuples, with each tuple containing an element and its priority level.

struct HeapPriorityQueue<Element> {
    var elements: [(element: Element, priority: Int)] = []
}

Next, we will implement the basic operations for a priority queue: enqueue, dequeue, and peek.

For the enqueue operation, we will append the element and its priority level to the elements array and then perform the heapify-up operation to ensure the heap property is maintained.

extension HeapPriorityQueue {

    mutating func enqueue(_ element: Element, withPriority priority: Int) {
        elements.append((element, priority))
        heapifyUp(from: elements.count - 1)
    }

    private mutating func heapifyUp(from index: Int) {
        let parent = parentIndex(of: index)
        guard !isRoot(index), elements[parent].priority > elements[index].priority else { return }
        swapElement(at: parent, with: index)
        heapifyUp(from: parent)
    }

    private func parentIndex(of index: Int) -> Int {
        return (index - 1) / 2
    }

    private func isRoot(_ index: Int) -> Bool {
        return index == 0
    }

    private mutating func swapElement(at index: Int, with otherIndex: Int) {
        elements.swapAt(index, otherIndex)
    }
}

For the dequeue operation, we will remove the root element (highest priority element) and then perform the heapify-down operation to ensure the heap property is maintained.

extension HeapPriorityQueue {
    mutating func dequeue() -> Element? {
        guard !elements.isEmpty else { return nil }
        swapElement(at: 0, with: elements.count - 1)
        let element = elements.removeLast()
        heapifyDown(from: 0)
        return element.element
    }

    private mutating func heapifyDown(from index: Int) {
        let childIndex = self.highestPriorityIndex(for: index)
        guard index != childIndex else { return }
        swapElement(at: index, with: childIndex)
        heapifyDown(from: childIndex)
    }

    private func highestPriorityIndex(for index: Int) -> Int {
        return highestPriorityIndex(of: index, and: highestPriorityIndex(of: index, and: rightChildIndex(of: index)))
    }

    private func highestPriorityIndex(of parentIndex: Int, and childIndex: Int) -> Int {
        guard childIndex < elements.count, elements[childIndex].priority < elements[parentIndex].priority else { return parentIndex }
        return childIndex
    }

    private func leftChildIndex(of index: Int) -> Int {
        return (2 * index) + 1
    }

    private func rightChildIndex(of index: Int) -> Int {
        return (2 * index) + 2
    }
}

For the peek operation, we will simply return the root element.

extension HeapPriorityQueue {
    func peek() -> Element? {
        return elements.first?.element
    }
}

Now we have a basic implementation of a priority queue using a heap. Conclusion In this tutorial, we explored multiple ways to implement a priority queue in Swift. We first implemented a priority queue using a sorted array, and then we implemented a priority queue using a heap. Both methods have their own advantages and disadvantages, and the appropriate method to use will depend on the specific needs of your application. If you are interested in learning more about priority queues and their implementation in Swift, I recommend checking out these resources:

• Priority Queues on Swift Algorithm Club
• Priority Queues on HackerEarth
• [Priority Queues on Wikipedia](https://en.wikipedia.org/wiki/Priority_Queue)