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

Очередь с приоритетом - это структура данных, где каждый элемент имеет приоритет, и извлечение всегда происходит элемента с наивысшим (или наинизшим) приоритетом, независимо от порядка добавления. В Go стандартная библиотека не предоставляет готовой реализации, но её можно построить на основе кучи (heap).

Реализация в Go использует интерфейс heap.Interface из пакета container/heap. Для этого нужно определить тип, реализующий методы Len(), Less(), Swap(), Push() и Pop(). Обычно в основе лежит срез структур, содержащих значение и приоритет.

Пример минимальной реализации для минимальной очереди (наименьший приоритет извлекается первым):

GO
type Item struct {
    Value    string
    Priority int
}

type PriorityQueue []*Item

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

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

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(*Item))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

Использование:

GO
pq := &PriorityQueue{}
heap.Init(pq)
heap.Push(pq, &Item{Value: "task1", Priority: 3})
heap.Push(pq, &Item{Value: "task2", Priority: 1})
item := heap.Pop(pq).(*Item) // извлекается task2 с приоритетом 1

Ключевой момент: heap.Init строит бинарную кучу за O(n), а операции Push и Pop работают за O(log n). Это эффективнее, чем поддержание отсортированного списка.