pattern heroPT–23LeetCode Extension

Куча и топ-K

Куча всегда держит наверху самый маленький (или самый большой) элемент и быстро обновляется, когда что-то добавили или забрали. Поэтому, чтобы взять лучшие k, не нужно сортировать всё.

Вариант
P09 Куча и топ-Kk наибольших · 1×

Пример задачи: найти 3 самых больших числа в [4, 1, 7, 3, 8, 2, 9].

4173829мин-кучаk = 3
ещё не прочитанотекущее число xв кучекорень, сравниваем с xвыброшеноответ

Начинаем с пустой мин-кучи

heap = []x = –
01/29
сначала · назад · пуск · шаг
Скорость
1function kLargest(nums, k):
2 heap = empty min-heap
3 for each x in nums:
4 if size of heap < k:
5 push x into heap
6 else if x > min of heap:
7 pop min from heap
8 push x into heap
9 return heap

← → шаг · пробел — пауза

Как узнать

k самых больших, малых, близких или частых элементов либо k-й из них, часто из длинного списка или потока.

Как решать такие задачи

  1. Переверни кучу: для k самых больших бери мин-кучу, для k самых малых — макс-кучу.
  2. Выбери ключ для сравнения: значение, счётчик из словаря, расстояние до точки.
  3. Заполни кучу до k элементов. Дальше новый элемент заменяет корень, только если он лучше корня.
  4. В конце в куче лежит ответ, а в её корне — k-й лучший элемент.

Вариант: Слияние k списков

То же, но в куче лежат первые элементы k отсортированных списков. Наверху всегда следующий элемент общего ответа, поэтому не нужно каждый раз сравнивать все k списков.

  1. Положи в кучу по одному кандидату от каждого списка — его первый узел, пустые списки пропусти. Куча сравнивает узлы по node.val.
  2. Достань наименьший узел и добавь его в ответ.
  3. Если у него есть следующий, положи node.next в кучу: теперь он кандидат от этого списка.
  4. Так же решаются k-й наименьший в матрице с отсортированными строками (достать k раз) и наименьший диапазон, покрывающий все списки (ещё следи за наибольшим кандидатом).

Вариант: Две кучи

То же, но куч две: одна держит меньшую половину чисел, другая — большую. Медиана всегда лежит наверху одной из них, и после каждого нового числа не нужно сортировать всё заново.

  1. Как узнать: числа приходят постепенно, а середина нужна снова и снова, или вообще нужно делить числа на нижнюю и верхнюю части.
  2. Держи две кучи: макс-кучу low для меньшей половины и мин-кучу high для большей.
  3. Каждое число клади в low, потом переноси верх low в high. Так всё в low остаётся не больше всего в high.
  4. Если high стала больше low, верни её верх обратно. Теперь в low столько же чисел или на одно больше.
  5. Ответ бери с верхов: при нечётном количестве — верх low, при чётном — среднее двух верхов.

Где встречается

  • Таймеры в Node.js. Библиотека libuv, на которой работает Node.js, хранит таймеры в куче: наверху всегда тот, что сработает раньше всех. Поэтому, чтобы понять, сколько ждать, ей не нужно перебирать все таймеры.
  • Python. heapq.nlargest(k, данные) держит кучу из k лучших и пропускает через неё остальные данные, а не сортирует всё.
  • RocksDB. RocksDB хранит данные в нескольких отсортированных файлах. Чтобы читать их по порядку, он сливает их через кучу, где наверху всегда следующий ключ.