Куча, стек, очередь, deque

Эти слова описывают контракт, а не конкретный массив.

Стек: положили последним — сняли первым. Это LIFO. Отмена, скобки, стек вызовов.

Очередь: первым пришёл — первым ушёл. Это FIFO. Воркеры, список задач.

Deque умеет оба конца. Двоичная куча (binary heap) — не «очередь с приоритетом вообще», а конкретная реализация: дерево в массиве, где родитель не хуже детей.

Пример. Стек тарелок: сняли верхнюю. Очередь в кассу: кто пришёл первым, того первым обслужили. Куча как структура — приём в больнице: на вершине всегда самый срочный. Не путайте с «кучей процесса», откуда GC забирает объекты. Слово одно, вещи разные.

Стек вызовов функции и stack как структура данных — разная жизнь, одна идея LIFO. Горутина растёт свой стек сама. Это не []int, который вы append'ите.

Priority queue на куче нужна планировщику, таймерам («ближайший дедлайн»), top-K, слиянию отсортированных потоков. Извлечение минимума из бинарной кучи — O(log n): сняли корень, на его место последний элемент, просеяли вниз. Подсмотреть минимум — O(1). После извлечения кучу надо восстановить. Поэтому «всегда O(1) без восстановления» — неверно.

Куча как массив

Индекс i, дети 2i+1 и 2i+2. Вставка — в конец и просеивание вверх, O(log n). Это не отсортированный массив. Порядок внутри уровня не обещан. Обещан только heap property: родитель не хуже детей.

Чтобы реализовать интерфейс heap.Interface в Go, нужны Len, Less, Swap, Push, Pop.

type minHeap []int

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

// heap.Init(&h); heap.Push(&h, 3); min := heap.Pop(&h).(int)

Очередь на слайсе

Стек на слайсе естественен: append и s[:len-1]. Очередь «головой в начале» через s = s[1:] выглядит O(1) по времени. Но оставляет неиспользуемый префикс backing array: len падает, cap спереди мёртвый. Долгая очередь так раздует память.

Пример. Слайс из 1000 задач. Сняли 900 с головы через s = s[1:]. Живых элементов 100, а массив на 1000 всё ещё держится: cap смотрит на старый префикс. Нужен ring buffer, смещение головы с периодическим compact, или контейнер из двух стеков.

Что выбрать

• Воркеры задач — FIFO, не стек: иначе последний запрос голодает первых.
• Таймауты и «кто раньше истёк» — куча по дедлайну.
• Отмена вложенных операций, парсер, undo — стек.
• Deque — скользящее окно, обе стороны очереди.