Priority Queue Implementation in Swift

1. Introduction

A PriorityQueue is a special type of queue in which each element has a priority. Elements with higher priorities are served before elements with lower priorities. This data structure is useful in scenarios where not all items are equal and certain items must be processed before others, such as in job scheduling or graph algorithms.

2. Implementation Steps

1. Define a PriorityQueue class or struct.

2. Use a private array to store the elements of the priority queue.

3. Define a method enqueue to add an item with a given priority.

4. Define a method dequeue to remove the item with the highest priority.

5. Provide a method peek to view the highest priority item without removing it.

6. Include a computed property isEmpty to check if the priority queue is empty.

3. Implementation in Swift

struct PriorityQueue<T> {
    private var elements: [(value: T, priority: Int)] = []
    // Enqueue: Add an item with a given priority
    mutating func enqueue(_ value: T, priority: Int) {
        elements.append((value, priority))
        elements.sort { $0.priority > $1.priority }
    }
    // Dequeue: Remove and return the highest priority item
    mutating func dequeue() -> T? {
        return isEmpty ? nil : elements.removeFirst().value
    }
    // Peek: Look at the highest priority item without removing it
    func peek() -> T? {
        return elements.first?.value
    }
    // Check if the priority queue is empty
    var isEmpty: Bool {
        return elements.isEmpty
    }
}
// Example Usage
var tasks = PriorityQueue<String>()
tasks.enqueue("Regular task", priority: 1)
tasks.enqueue("High priority task", priority: 3)
tasks.enqueue("Medium priority task", priority: 2)
print("After enqueues: \(tasks)")
print("Peek: \(tasks.peek() ?? "None")")
print("Dequeue: \(tasks.dequeue() ?? "None")")
print("After dequeue: \(tasks)")

Output:

After enqueues: PriorityQueue<String>(elements: [("High priority task", 3), ("Medium priority task", 2), ("Regular task", 1)])
Peek: High priority task
Dequeue: High priority task
After dequeue: PriorityQueue<String>(elements: [("Medium priority task", 2), ("Regular task", 1)])

Explanation:

1. A PriorityQueue is implemented as a generic struct. Each element in the queue is represented as a tuple containing a value and its associated priority.

2. Within the PriorityQueue, a private array named elements is used to manage the elements.

3. The enqueue method appends an item with its given priority to the elements array. The elements are then sorted in descending order based on priority.

4. The dequeue method removes and returns the first item (highest priority) from the elements array. If the priority queue is empty, it returns nil.

5. The peek method provides a way to view the highest priority item without removing it.

6. The isEmpty computed property checks if the elements array is empty, indicating the state of the priority queue.