> Что такое очередь с приоритетом и как она реализуется (Go)

Короткий ответ

Очередь с приоритетом - это структура данных, где каждый элемент имеет приоритет, и извлечение всегда происходит в порядке убывания приоритета, а не в порядке добавления. В Go стандартная реализация - через container/heap с интерфейсом heap.Interface. Базовая структура - бинарная куча (binary heap), которая обеспечивает сложность O(log n) для вставки и извлечения.

Подробное объяснение

Очередь с приоритетом (priority queue) отличается от обычной FIFO-очереди тем, что порядок извлечения определяется приоритетом элемента, а не временем его добавления. Основные операции:

• Push - добавление элемента с приоритетом, O(log n)
• Pop - извлечение элемента с максимальным (или минимальным) приоритетом, O(log n)
• Peek - просмотр верхнего элемента без извлечения, O(1)

В Go нет встроенной структуры priority queue, но есть пакет container/heap, который предоставляет общие функции для работы с любой кучей. Чтобы использовать его, нужно реализовать интерфейс:

GO
type Interface interface {
    sort.Interface
    Push(x any)
    Pop() any
}

sort.Interface требует методы Len(), Less(i, j int) bool и Swap(i, j int). Ключевой момент - метод Less определяет порядок приоритета: если вернуть pq[i].priority > pq[j].priority, получим max-heap, если < - min-heap.

Реализация через бинарную кучу хранит элементы в массиве, где для индекса i дети находятся на позициях 2*i+1 и 2*i+2. Свойство кучи гарантирует, что корень всегда имеет наивысший приоритет. При вставке элемент добавляется в конец и "всплывает" вверх, при извлечении корень заменяется последним элементом и "просеивается" вниз.

На практике

Priority queue часто используется в backend-разработке для:

• Планировщиков задач (task schedulers) - обработка задач с наибольшим приоритетом
• Обработки сетевых запросов с разными уровнями важности
• Реализации алгоритмов: Дейкстра, A*, поиск k ближайших элементов
• Rate limiting и очередей сообщений с приоритетами

В Go важно помнить, что container/heap работает с интерфейсом, поэтому нужно явно вызывать heap.Init, heap.Push и heap.Pop, а не методы самого типа. Типичная ошибка - использовать Push и Pop напрямую из вашего типа, что ломает инвариант кучи.

Пример кода

GO
package main

import (
    "container/heap"
    "fmt"
)

type Item struct {
    value    string
    priority int
    index    int // не обязателен, но полезен для update
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// max-heap: больший priority - выше
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x any) {
    item := x.(*Item)
    item.index = len(*pq)
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil // избегаем утечки памяти
    item.index = -1
    *pq = old[0 : n-1]
    return item
}

func main() {
    pq := &PriorityQueue{}
    heap.Init(pq)

    heap.Push(pq, &Item{value: "low", priority: 1})
    heap.Push(pq, &Item{value: "high", priority: 10})
    heap.Push(pq, &Item{value: "mid", priority: 5})

    for pq.Len() > 0 {
        item := heap.Pop(pq).(*Item)
        fmt.Printf("%s (priority %d)\n", item.value, item.priority)
    }
    // Output:
    // high (priority 10)
    // mid (priority 5)
    // low (priority 1)
}

Как отвечать на собеседовании

Начните с определения и ключевого отличия от обычной очереди. Затем упомяните, что в Go нет готовой реализации, но есть container/heap, и объясните, как работает интерфейс. Обязательно скажите про сложность операций - O(log n). Если спросят про альтернативы, можно упомянуть sorted slice (вставка O(n)) или balanced BST (сложнее в реализации). Покажите понимание trade-off между простотой бинарной кучи и её ограничениями - например, нет эффективного поиска произвольного элемента.

Что проверяет интервьюер

• Понимание разницы между FIFO и priority queue
• Знание базовой структуры - бинарная куча и её свойства
• Умение работать с интерфейсами в Go (heap.Interface, sort.Interface)
• Понимание сложности операций и когда применять эту структуру
• Практические навыки: реализация Less для max/min heap, корректное использование heap.Push/heap.Pop

Типичные ошибки

• Вызов Push/Pop напрямую на типе вместо heap.Push/heap.Pop - ломает инвариант кучи
• Путаница в Less: для max-heap нужно > , для min-heap - <
• Забывают вызвать heap.Init перед первым использованием
• Не учитывают, что Pop возвращает any, и забывают про type assertion
• Хранят элементы по значению, а не по указателю - при Swap копируются структуры, что может быть неэффективно
• Не освобождают память в Pop (не обнуляют последний элемент)