Как разработчик, вы могли сталкиваться с ситуациями, когда вам нужно расставить приоритеты для определенных задач или элементов над другими. Один из способов справиться с этим — использовать очередь с приоритетом. Очередь с приоритетом — это структура данных, которая позволяет хранить элементы и назначать им уровень приоритета, при этом элементы с наивысшим приоритетом обрабатываются в первую очередь.

В этом руководстве мы рассмотрим несколько способов реализации приоритетной очереди в Swift и то, как они работают.

Использование отсортированного массива

Одним из способов реализации приоритетной очереди является использование отсортированного массива. Для этого мы создадим структуру с именем PriorityQueue с общим типом Element. Мы также создадим свойство с именем elements, которое будет массивом кортежей, где каждый кортеж содержит элемент и его уровень приоритета.

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

Далее мы реализуем основные операции для приоритетной очереди: постановка в очередь, удаление из очереди и просмотр.

Для операции постановки в очередь мы просто добавим элемент и его уровень приоритета в массив elements, а затем отсортируем массив на основе уровня приоритета.

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

Для операции удаления из очереди мы удалим первый элемент в массиве, который будет иметь наивысший приоритет из-за сортировки.

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

Для операции просмотра мы просто вернем первый элемент массива.

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

Теперь у нас есть базовая реализация приоритетной очереди с использованием отсортированного массива.

Использование кучи

Другой способ реализации приоритетной очереди — использование кучи. Куча — это полное двоичное дерево, в котором родительский узел всегда больше или равен своим дочерним элементам (для максимальной кучи) или меньше или равен своим дочерним элементам (для минимальной кучи). Это гарантирует, что самое высокое или самое низкое значение всегда находится в корне дерева.

Чтобы реализовать приоритетную очередь с использованием кучи, мы создадим структуру с именем HeapPriorityQueue с общим типом Element. Мы также создадим свойство с именем elements, которое будет массивом кортежей, где каждый кортеж содержит элемент и его уровень приоритета.

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

Далее мы реализуем основные операции для приоритетной очереди: постановка в очередь, удаление из очереди и просмотр.

Для операции постановки в очередь мы добавим элемент и его уровень приоритета в массив elements, а затем выполним операцию heapify-up, чтобы обеспечить сохранение свойства кучи.

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

Для операции удаления из очереди мы удалим корневой элемент (элемент с наивысшим приоритетом), а затем выполним операцию heapify-down, чтобы обеспечить сохранение свойства кучи.

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

Для операции просмотра мы просто вернем корневой элемент.

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

Теперь у нас есть базовая реализация приоритетной очереди с использованием кучи. Заключение В этом руководстве мы рассмотрели несколько способов реализации приоритетной очереди в Swift. Сначала мы реализовали очередь с приоритетом, используя отсортированный массив, а затем реализовали очередь с приоритетом, используя кучу. Оба метода имеют свои преимущества и недостатки, и выбор подходящего метода будет зависеть от конкретных потребностей вашего приложения. Если вам интересно узнать больше об очередях с приоритетом и их реализации в Swift, я рекомендую ознакомиться с этими ресурсами: