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

Что проверяют

Понимаете ли вы, что очередь с приоритетом это интерфейс, а куча это его реализация, и знаете ли, как этот интерфейс подключается в Go через пакет container/heap. Заодно проверяют, умеете ли вы аккуратно реализовать стандартный интерфейс на срезе с указателем.

Как отвечать

Очередь с приоритетом отдаёт не первый положенный элемент, а самый приоритетный. Операции: вставка и извлечение экстремума за O(log n), просмотр вершины за O(1), построение из готового среза за O(n).

Готового типа в стандартной библиотеке Go нет: есть container/heap, который работает поверх вашего среза, если тот реализует sort.Interface плюс методы Push и Pop.

type Item struct {
	value    string
	priority int
}

type PQ []*Item

func (q PQ) Len() int           { return len(q) }
func (q PQ) Less(i, j int) bool { return q[i].priority > q[j].priority }
func (q PQ) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }
func (q *PQ) Push(x any)        { *q = append(*q, x.(*Item)) }

func (q *PQ) Pop() any {
	old := *q
	n := len(old)
	it := old[n-1]
	*q = old[:n-1]
	return it
}

Дальше работают только через heap.Push(&q, item) и heap.Pop(&q).(*Item): ваши методы это кирпичи, а восстановление инварианта кучи делает пакет. Из применений уместно назвать планировщики задач, слияние отсортированных потоков и алгоритмы поиска кратчайшего пути.

Где спотыкаются

Зовут q.Push напрямую вместо heap.Push. Метод кладёт элемент в конец среза и не просеивает его вверх, куча ломается молча, а извлечение начинает выдавать не тот элемент.

Путают направление сравнения. Less с оператором больше даёт max-heap, с меньше min-heap; алгоритму кратчайшего пути нужен минимум, и перепутанный знак даёт работающий, но неверный результат.

Забывают про индекс элемента в структуре. Без поля, которое обновляется в Swap, нельзя вызвать heap.Fix или heap.Remove, то есть нельзя изменить приоритет уже добавленной задачи, а именно это обычно и требуется.