Куча и приоритетные очереди

Перед началом: сортировки и их сравнение (модуль 8). Инструменты: Go 1.27, container/heap, slices. Трудоёмкость: ~6 ч (теория 2.5 ч · практика 3.5 ч).

🔥 Инцидент: «Топ-10 отчётов на 100 млн событий»

Аналитический воркер каждую ночь собирал топ-10 самых «тяжёлых» отчётов по score из дневного журнала событий. Реализация была очевидной: прочитать весь журнал в память, отсортировать через slices.Sort и взять первые десять. На стенде с двумя миллионами событий это занимало секунды и гигабайт памяти — терпимо.

В проде журнал — 100 млн событий: воркер захватывал десятки гигабайт, сортировка шла минутами, и на очередном запуске его убил OOM-killer; ретрай повторил судьбу. Отчёты отсутствовали три ночи, а виноватым выглядел рост данных, а не выбор алгоритма.

Для топ-10 не нужен порядок всех 100 миллионов: нужна структура размера k, которая знает «слабейшего из отобранных» и заменяет его кандидатом. Это min-куча размера k: O(n log k) времени и O(k) памяти. Дальше — куча до дна: дерево в срезе, sift-up и sift-down, сборка за O(n), грабли container/heap, top-K, k-way merge и медиана потока.

📖 Теория

9.1 Куча — полное дерево в срезе

Куча — полное двоичное дерево (уровни заполняются слева направо) плюс свойство: в min-куче родитель не больше детей. Минимум всегда в корне, а срез хранит дерево без указателя — связи задаются индексами.

go
// parent(i) = (i-1)/2  ·  left(i) = 2i+1  ·  right(i) = 2i+2
h := []int{1, 3, 5, 4, 8, 7} // min-heap: родитель не больше детей
fmt.Println(h[0], h[1], h[2]) // 1 3 5 — минимум всегда в корне

Плотный срез вместо указателей — скорость, кэш и память; высота кучи — log₂n (полное дерево как форму разберём в §11.1). Куча не сортирована: отвечает только «кто минимален», а порядок достаётся повторными pop — это и есть heap sort.

9.2 sift-up и sift-down: push и pop за O(log n)

Обе операции чинят ровно одно нарушение и идут по одной ветке высотой не больше log n: push дописывает элемент в конец и всплывает, пока он меньше родителя; pop ставит в корень последний и погружает его.

go
// siftUp: элемент всплывает, меняясь с родителем, пока меньше него.
func (h *minHeap) siftUp(i int) {
	for i > 0 && h.data[(i-1)/2] > h.data[i] { // пока мешает родитель
		p := (i - 1) / 2
		h.data[p], h.data[i] = h.data[i], h.data[p]
		i = p
	}
}

Ключ к отладке: после операции нарушена одна ветка — ошибка в sift.

9.3 build-heap за O(n), а не O(n log n)

n вызовов push строят кучу за O(n log n). Дешевле — heapify: он идёт снизу вверх от последнего внутреннего узла (len/2 − 1). Почему суммарно O(n): у массового нижнего уровня высота 0, высоту h имеют лишь ~n/2^(h+1) узлов, и сумма высот по всем узлам ≈ 2n.

go
// heapify строит кучу из готового среза за O(n), снизу вверх.
func heapify(data []int) *minHeap {
	h := &minHeap{data: data}
	for i := len(data)/2 - 1; i >= 0; i-- {
		h.siftDown(i) // порядок «от листьев к корню» обязателен
	}
	return h
}

Вывод: весь массив сразу — heapify, элементы по одному — n вставок.

9.4 container/heap: интерфейс и типичные грабли

container/heap работает с любым типом: достаточно отдать Len/Less/Swap и методы Push/Pop.

go
// Кучей для container/heap становится любой тип с пятью методами.
type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any { // heap.Pop уже перенёс корень в конец
	old := *h
	*h = old[:len(old)-1]
	return old[len(old)-1]
}

Использование: heap.Init(h) — O(n), далее heap.Push(h, x) и heap.Pop(h) — функции пакета, не методы контейнера.

• вызвать h.Push(x) напрямую — инвариант сломан, нужен heap.Push;
• heap.Pop на пустой куче паникует — проверяйте Len;
• правка приоритета по индексу без heap.Fix(h, i) молча ломает кучу;
• элементы ходят через any: бокс и аллокации; своя куча дешевле.

9.5 Где это в проде: top-K, k-way merge, медиана потока

Top-K — прямой ответ на инцидент: min-куча размера k, кандидат слабее корня уходит мимо, сильнее — вытесняет корень.

go
// В куче размера k корень — минимум из отобранных: он и вытесняется.
for _, v := range nums {
	if len(h.data) < k {
		h.push(v)
	} else if v > h.data[0] {
		h.data[0] = v
		h.siftDown(0)
	}
}

K-way merge — слить k отсортированных срезов: «собрать всё и отсортировать» — O(N log N), куча из k голов — O(N log k). Из кучи снимается минимум, а на его место возвращается элемент того же потока.

Медиана потока — две кучи: нижняя половина в max-куче (эмуляция отрицанием), верхняя в min-куче, размеры различаются не больше чем на единицу: add — O(log n), median — O(1) вместо пересортировки.

Приоритетные очереди: пул задач «сначала дедлайновые», таймеры с backoff, фильтры «самый частый нарушитель». Задел: Дейкстра в модуле 15 — это куча, из которой достаётся ближайшая непосещённая вершина.

9.6 Компромиссы

Правило: «только k лучших» — куча размера k, «весь порядок» — сортировка, «минимум и обход по возрастанию» — BST (модуль 12).

💻 Практика

1. Своя куча целиком. Реализуйте min-heap с push, pop, peek и heapify. Тесты: pop отдаёт по возрастанию (сверьте со slices.Sort), peek не меняет кучу, пустая куча. Со счётчиком обменов сравните на обратно отсортированных 9 числах n вставок против heapify; почему цикл heapify нельзя запускать от корня вниз?
2. Top-K частых слов. Постройте частоты слов (модуль 4) и извлеките top-K min-кучей размера k; при равной частоте — алфавитный порядок. Тесты: k больше числа уникальных слов, k = 1, равные частоты, пустой вход. Почему «отсортировать всё» проигрывает на 100 млн слов?
3. K-way merge. mergeK(streams [][]int) для k отсортированных срезов через кучу из (значение, поток, позиция). Тесты: один поток, пустые потоки вперемешку, дубликаты на стыках, отрицательные числа. Сравните число сравнений с «сложить и отсортировать» при k = 8.
4. Медиана потока. Структура с add и median на двух кучах. Тесты: одно число, чётное число элементов (среднее середин), монотонный поток, перевес нижней половины. Сравните с «пересортировать на каждый элемент» на 1000 чисел: во сколько раз медленнее наивная версия?
5. Приоритеты с heap.Fix. На container/heap соберите очередь задач (id, priority) с push, pop, raise(id, delta), меняющую приоритет на месте через heap.Fix. Тесты: без Fix порядок неверный, с Fix — корректный; raise для отсутствующего id — ошибка.

🧩 Quiz

✅ Итоги модуля

• Куча — полное дерево в срезе: минимум в корне за O(1), push и pop — один sift по ветке высотой log n.
• heapify из готового среза — O(n); n вставок подряд — другой, худший алгоритм: выбор зависит от того, как приходят данные.
• container/heap — готовая очередь ценой any-бокса: heap.Fix после правки приоритета, Pop на пустой паникует.
• Top-K — O(n log k) и O(k) памяти; k-way merge — O(N log k); медиана потока — две кучи; приоритетная очередь — фундамент Дейкстры (модуль 15).

🔗 Мостик к Модулю 10

Куча отвечает «кто лучший», но не «где элемент»: доступа по индексу у неё нет. Дальше — самый дешёвый способ найти элемент и границу в упорядоченных данных: «Бинарный поиск и поиск по ответу» — инвариант интервала, lower/upper bound, sort.Search и поиск по монотонному предикату.