K-way merge: слияние k отсортированных списков через кучу
Паттерн K-way merge на примерах: Merge k Sorted Lists, k-й наименьший в отсортированной матрице, Smallest Range Covering k Lists и внешняя сортировка. Куча на k элементов, код на Python.
Коротко
| Задача | Решение | Время | Память |
|---|---|---|---|
| Слить k отсортированных массивов | min-куча из «голов» | + ответ | |
| Merge k Sorted Lists (LeetCode 23) | куча или попарное слияние | / | |
| k-й наименьший в матрице (LC 378) | куча по строкам или бинпоиск по ответу | / | / |
| Smallest Range Covering k Lists (LC 632) | куча + текущий максимум | ||
| Внешняя сортировка | отсортированные прогоны + k-way merge | , мало проходов по диску |
Здесь — общее число элементов, — число списков.
- В куче лежит ровно по одному кандидату от каждого списка — его текущая «голова». Достали минимум, положили следующий элемент из того же списка.
- Куча размера даёт на шаг вместо на линейный поиск минимума.
- В кортеже для кучи всегда держите индекс списка: он разруливает равные значения и не даёт Python сравнивать узлы.
- Паттерн узнаётся по фразе «даны несколько отсортированных последовательностей» — даже если они спрятаны в строках матрицы или генерируются на лету.
Откуда паттерн и как его узнать
Слияние двух отсортированных списков — база, её подробно разбирает статья про объединение двух отсортированных списков: два указателя, на каждом шаге берём меньшую голову. K-way merge обобщает это на источников.
С двумя указателями выбрать меньшую голову — одно сравнение. С указателями наивный выбор стоит , и при элементах получаем . Нужна структура, которая хранит голов и быстро отдаёт минимальную, — это min-куча, она же приоритетная очередь. Как куча устроена внутри, описано в статье про бинарную кучу; здесь нам хватит heapq.
Признаки задачи на k-way merge:
- на входе отсортированных массивов, списков, файлов, потоков;
- есть матрица, где отсортированы строки (или строки и столбцы), и спрашивают про порядок элементов;
- спрашивают «k-й наименьший», «первые k пар», «наименьший диапазон», и множество кандидатов естественно раскладывается на отсортированные цепочки;
- данных больше, чем памяти, и их нужно отсортировать.
Базовый шаблон: слить k массивов
import heapq def merge_k_arrays(arrays): # (значение, номер массива, позиция в массиве) heap = [] for i, arr in enumerate(arrays): if arr: heap.append((arr[0], i, 0)) heapq.heapify(heap) result = [] while heap: value, i, j = heapq.heappop(heap) result.append(value) if j + 1 < len(arrays[i]): heapq.heappush(heap, (arrays[i][j + 1], i, j + 1)) return result print(merge_k_arrays([[1, 4, 7], [2, 5], [3, 6, 9]])) # [1, 2, 3, 4, 5, 6, 7, 9]
Как это работает на примере:
| Шаг | Куча (значение, массив) | Достали | Положили |
|---|---|---|---|
| 0 | (1,0) (2,1) (3,2) | — | — |
| 1 | (2,1) (3,2) (4,0) | 1 | 4 из #0 |
| 2 | (3,2) (4,0) (5,1) | 2 | 5 из #1 |
| 3 | (4,0) (5,1) (6,2) | 3 | 6 из #2 |
| 4 | (5,1) (6,2) (7,0) | 4 | 7 из #0 |
| 5 | (6,2) (7,0) | 5 | #1 пуст |
Инвариант: в куче не больше одного элемента от каждого массива, и это наименьший ещё не выведенный элемент своего массива. Значит, минимум кучи — минимум среди всего, что осталось. Отсюда корректность.
Сложность. Каждый из элементов один раз попадает в кучу и один раз из неё уходит: . heapify на старте — . Память — на кучу плюс сам ответ.
Готовое в стандартной библиотеке
В Python то же самое делает heapq.merge. Он ленивый: возвращает итератор и держит в памяти только головы.
import heapq print(list(heapq.merge([1, 4, 7], [2, 5], [3, 6, 9]))) # [1, 2, 3, 4, 5, 6, 7, 9] # Поддерживает key и reverse — входы тогда должны быть отсортированы так же words = heapq.merge(['b', 'ccc'], ['aa', 'dddd'], key=len) print(list(words)) # ['b', 'aa', 'ccc', 'dddd']
На собеседовании heapq.merge стоит упомянуть, но реализацию всё равно попросят написать руками: проверяют именно идею с кучей.
Merge k Sorted Lists
LeetCode 23, Hard. Даны отсортированных односвязных списков, нужно слить их в один.
Вход: [1→4→5, 1→3→4, 2→6] Выход: 1→1→2→3→4→4→5→6
Наивные решения
Собрать всё и отсортировать. Пройти списки, сложить значения в массив, sort(), собрать новый список. по времени и по памяти. Работает, но не использует то, что списки уже отсортированы, — интервьюер спросит, можно ли лучше.
Сливать по одному. result = merge(result, lists[i]) в цикле. Выглядит естественно, но result растёт: на -м шаге он длиной около , где — длина одного списка. Сумма даёт . При это уже медленно.
Решение через кучу
import heapq class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def merge_k_lists(lists):
# i — номер списка: при равных val сравнение дойдёт до него, а не до node
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
heapq.heapify(heap)
dummy = tail = ListNode()
while heap:
_, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
Узлы не копируются, мы только переставляем указатели — дополнительная память $O(k)$. Почему в кортеже нужен `i` и что будет без него, подробно объяснено в разделе про несравнимые данные статьи [о приоритетной очереди](/ru/blog/priority-queue): без него на двух равных `val` Python попытается сравнить два `ListNode` и упадёт с `TypeError`.
Индекс `i` уникален для каждого списка, а в куче одновременно лежит не больше одного узла из каждого списка. Поэтому пара `(val, i)` всегда различна, и до `node` сравнение никогда не доходит.
### Решение «разделяй и властвуй»
Вторая классическая идея — сливать списки попарно, как в [сортировке слиянием](/ru/blog/merge-sort): сначала пары (0,1), (2,3), …, потом пары результатов, и так далее.
```python
def merge_two(a, b):
dummy = tail = ListNode()
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
def merge_k_lists_dc(lists):
if not lists:
return None
step = 1
while step < len(lists):
for i in range(0, len(lists) - step, step * 2):
lists[i] = merge_two(lists[i], lists[i + step])
step *= 2
return lists[0]
Уровней слияния , на каждом уровне все узлов проходят через merge_two один раз — итого тот же . Зато нет кучи: дополнительная память (итеративная версия, без рекурсии), и константа обычно меньше.
| Подход | Время | Доп. память | Когда выбрать |
|---|---|---|---|
| Собрать и отсортировать | быстрый прототип, сравнимо с | ||
| По одному | никогда, кроме | ||
| Куча | данные приходят потоком, списки разной длины | ||
| Попарное слияние | все списки уже в памяти |
Важное отличие: куча работает со стримами. Ей не нужно знать списки целиком — достаточно уметь брать следующий элемент. Попарное слияние требует, чтобы все входы были доступны сразу. На этом построена внешняя сортировка, о ней ниже.
k-й наименьший элемент в отсортированной матрице
LeetCode 378, Medium. Матрица , каждая строка и каждый столбец отсортированы по возрастанию. Найти -й наименьший элемент (с учётом повторов).
matrix = [[ 1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8 → 13
Отсортированный порядок: 1, 5, 9, 10, 11, 12, 13, 13, 15.
Решение через кучу
Каждая строка — отсортированный список. Значит, перед нами задача «слить списков», только всё слияние не нужно: достаточно остановиться на -м шаге.
import heapq def kth_smallest(matrix, k): n = len(matrix) # Строк больше k брать незачем: ответ точно в первых k строках heap = [(matrix[r][0], r, 0) for r in range(min(n, k))] heapq.heapify(heap) for _ in range(k - 1): _, r, c = heapq.heappop(heap) if c + 1 < n: heapq.heappush(heap, (matrix[r][c + 1], r, c + 1)) return heap[0][0] m = [[1, 5, 9], [10, 11, 13], [12, 13, 15]] print(kth_smallest(m, 8)) # 13
Выбрасываем из кучи минимум, и на вершине остаётся ответ. Время , память .
Отсортированность столбцов здесь использована лишь слегка — в отсечении строк дальше -й. Для этого решения хватило бы и отсортированных строк.
Бинарный поиск по значению
Когда порядка , куча делает — почти как полная сортировка. Сортированные столбцы позволяют лучше: бинарный поиск по ответу. Ищем наименьшее значение , для которого элементов не меньше .
Сколько элементов , считается за «лесенкой»: идём по строкам сверху вниз, а указатель столбца двигаем только влево — в следующей строке все элементы не меньше, чем в предыдущей, поэтому граница не сдвигается вправо.
def kth_smallest_bs(matrix, k): n = len(matrix) def count_le(x): count, col = 0, n - 1 for row in matrix: while col >= 0 and row[col] > x: col -= 1 count += col + 1 return count lo, hi = matrix[0][0], matrix[-1][-1] while lo < hi: mid = (lo + hi) // 2 if count_le(mid) >= k: hi = mid else: lo = mid + 1 return lo
Время , где — разность максимума и минимума, память . Почему ответ — обязательно элемент матрицы, хотя мы перебираем произвольные числа: lo — наименьшее с count_le(x) >= k, а при между двумя соседними значениями матрицы счётчик не меняется. Значит, минимальное такое совпадает с каким-то элементом.
На собеседовании хорошо рассказать оба варианта: куча — как прямое применение k-way merge, бинпоиск — как оптимизация при больших .
Родственная задача: k пар с наименьшими суммами
LeetCode 373: даны два отсортированных массива, вернуть пар с наименьшими суммами. Это та же матрица в неявном виде: строка — суммы nums1[i] + nums2[j] по всем , и она отсортирована. Строить матрицу не нужно, элементы считаются на лету.
import heapq def k_smallest_pairs(nums1, nums2, k): if not nums1 or not nums2: return [] heap = [(nums1[i] + nums2[0], i, 0) for i in range(min(len(nums1), k))] heapq.heapify(heap) result = [] while heap and len(result) < k: _, i, j = heapq.heappop(heap) result.append([nums1[i], nums2[j]]) if j + 1 < len(nums2): heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1)) return result print(k_smallest_pairs([1, 7, 11], [2, 4, 6], 3)) # [[1, 2], [1, 4], [1, 6]]
, где — длина nums1. Это частый приём: «списки» в k-way merge могут быть не данными, а правилом генерации следующего кандидата.
Smallest Range Covering Elements from K Lists
LeetCode 632, Hard. Даны отсортированных списков. Найти наименьший диапазон , в который попадает хотя бы по одному числу из каждого списка. При равной длине выбирается диапазон с меньшим .
[[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]] → [20, 24]
Идея
Возьмём по одному элементу из каждого списка. Такой набор задаёт диапазон от минимума до максимума набора, и он покрывает все списки. Как его сузить? Максимум уменьшить нельзя — элементы в списках только растут. Остаётся поднять минимум: заменить его на следующий элемент из того же списка.
Это ровно k-way merge, к которому добавлена одна переменная — текущий максимум среди голов. Минимум даёт вершина кучи.
import heapq def smallest_range(nums): heap = [(row[0], i, 0) for i, row in enumerate(nums)] heapq.heapify(heap) current_max = max(row[0] for row in nums) best = [heap[0][0], current_max] while True: value, i, j = heapq.heappop(heap) if current_max - value < best[1] - best[0]: best = [value, current_max] if j + 1 == len(nums[i]): # Список i кончился: дальше нельзя покрыть его элементом return best nxt = nums[i][j + 1] current_max = max(current_max, nxt) heapq.heappush(heap, (nxt, i, j + 1)) print(smallest_range([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]])) # [20, 24]
Пройдём пример по шагам (в скобках — головы трёх списков):
| Головы | min | max | Диапазон | Лучший |
|---|---|---|---|---|
| (4, 0, 5) | 0 | 5 | [0, 5] | [0, 5] |
| (4, 9, 5) | 4 | 9 | [4, 9] | [0, 5] |
| (10, 9, 5) | 5 | 10 | [5, 10] | [0, 5] |
| (10, 9, 18) | 9 | 18 | [9, 18] | [0, 5] |
| (10, 12, 18) | 10 | 18 | [10, 18] | [0, 5] |
| (15, 12, 18) | 12 | 18 | [12, 18] | [0, 5] |
| (15, 20, 18) | 15 | 20 | [15, 20] | [0, 5] |
| (24, 20, 18) | 18 | 24 | [18, 24] | [0, 5] |
| (24, 20, 22) | 20 | 24 | [20, 24] | [20, 24] |
Диапазоны той же длины 5 ([4, 9], [5, 10], [15, 20]) лучший не заменяют — работает строгое <. После последней строки минимум 20 уходит из кучи, а следующего элемента во втором списке нет — выходим с ответом [20, 24].
Почему останавливаемся, когда кончился один список. Минимум набора — последний элемент списка . Чтобы получить новый диапазон, нужно поднять минимум, то есть заменить этот элемент следующим из списка , — а его нет. Любой диапазон с началом правее этого элемента вообще не покрывает список , так что проверять больше нечего.
Сложность. по времени, по памяти. Строгое < при сравнении длины гарантирует, что при равенстве останется диапазон с меньшим началом: минимумы мы перебираем по возрастанию.
Есть и альтернатива без кучи: слить все элементы в один массив пар (значение, номер списка), отсортировать и найти минимальное окно, где встречаются все номеров, — классическое скользящее окно. Это и памяти — проще доказать, но тяжелее по ресурсам.
Внешняя сортировка
Главное «промышленное» применение k-way merge. Задача: отсортировать файл, который не помещается в оперативную память. Скажем, 100 ГБ чисел при 2 ГБ памяти. Такое спрашивают и на алгоритмической секции, и на системном дизайне («отсортируй логи за месяц», «найди дубликаты в огромном файле»).
Двухфазный алгоритм
- Фаза прогонов (runs). Читаем вход кусками размером с доступную память, каждый кусок сортируем обычной сортировкой и пишем на диск отдельным файлом. Получаем отсортированных файлов.
- Фаза слияния. Открываем все 50 файлов, на каждый выделяем буфер чтения, и сливаем их кучей на 50 элементов в выходной файл.
Каждый байт читается и пишется по два раза — по разу в каждой фазе. Для диска это главное: счёт идёт не на сравнения, а на число проходов по данным и на то, чтобы чтение было последовательным.
import heapq import os import tempfile from itertools import islice def external_sort(src_path, dst_path, chunk_lines=100_000): run_paths = [] # Фаза 1: режем вход на куски, которые помещаются в память with open(src_path) as src: while True: chunk = [int(line) for line in islice(src, chunk_lines)] if not chunk: break chunk.sort() fd, path = tempfile.mkstemp(suffix='.run') with os.fdopen(fd, 'w') as run: run.writelines(f'{x}\n' for x in chunk) run_paths.append(path) # Фаза 2: k-way merge всех прогонов за один проход runs = [open(path) for path in run_paths] try: streams = [(int(line) for line in run) for run in runs] with open(dst_path, 'w') as dst: dst.writelines(f'{x}\n' for x in heapq.merge(*streams)) finally: for run, path in zip(runs, run_paths): run.close() os.remove(path)
Во второй фазе в памяти одновременно живут только голов плюс буферы открытых файлов — объём исходного файла здесь роли не играет. Python буферизует чтение сам; в реальной системе размер буферов подбирают явно.
Что спросят дальше
Сколько файлов можно слить за раз? Каждому входу нужен буфер, иначе чтение превратится в случайные мелкие обращения к диску. При памяти и буфере сливаем до файлов (один буфер — на выход). 2 ГБ и буфер 32 МБ дают около 60 входов. Если прогонов больше, слияние делают в несколько проходов: число проходов — , где — сколько файлов сливаем за раз. Поэтому выгодно делать большим: это и есть смысл k-way вместо попарного слияния. Попарное на 1000 прогонов — 10 проходов по всем данным, слияние по 99 — 2 прохода.
Как получить меньше прогонов? Алгоритм replacement selection: вместо «прочитал кусок — отсортировал» держим кучу размером с память, выводим из неё минимум и на его место читаем следующий элемент входа. Если новый элемент меньше только что выведенного, в текущий прогон он уже не попадёт — его откладывают в следующий. Прогон заканчивается, когда в куче остались только отложенные. На случайных данных прогоны получаются в среднем вдвое длиннее памяти, на почти отсортированных — гораздо длиннее.
Чем заменить кучу? В СУБД и библиотеках внешней сортировки часто используют турнирное дерево проигравших (loser tree): после извлечения минимума оно делает ровно сравнений по пути от листа к корню, а куче при просеивании вниз нужно примерно вдвое больше — по два сравнения на уровень. Асимптотика та же.
Где это живёт в реальности. Внешняя сортировка в СУБД (сортировки и merge join при нехватке памяти), compaction в LSM-деревьях (LevelDB, RocksDB, Cassandra сливают отсортированные SSTable-файлы), MapReduce: каждый reducer сливает отсортированные куски от многих mapper'ов. Утилита sort в GNU coreutils тоже умеет сортировать файлы больше памяти через временные файлы и слияние.
Типичные ошибки
- Нет индекса в кортеже.
(node.val, node)падает на равных значениях сTypeError: '<' not supported. Всегда(value, list_index, ...). - Пустые списки. Пустой вход надо отфильтровать до
heapify, иначеarr[0]упадёт сIndexError. В Merge k Sorted Lists во входе бываютNoneи даже пустой массивlists = []. - Положили в кучу все элементы сразу. Это уже не k-way merge, а heap sort: времени и памяти. Смысл паттерна — куча размера .
- Забыли положить следующий элемент. После
heappopнужно добавить следующий элемент того же списка, а не любого. Иначе нарушается инвариант «по одному от каждого». - Сравнили с наивным неправильно. Слияние по одному — не , а . Интервьюеры любят просить оценить именно его.
- В Smallest Range обновляют максимум не там.
current_maxрастёт только при добавлении нового элемента и никогда не уменьшается: вытолкнутый минимум на максимум не влияет. - В матрице берут k строк, когда строк меньше.
range(min(n, k)), а неrange(k).
Где встречается на собеседованиях
Merge k Sorted Lists — одна из самых известных Hard-задач, она есть почти в любом списке «топ задач для собеседования». Обычно её дают после разминки на слияние двух списков и смотрят, предложит ли кандидат кучу сам и сумеет ли оценить наивный вариант.
Типичные продолжения:
- «А если списки не помещаются в память / приходят по сети?» — переход к внешней сортировке и стримингу, куча здесь выигрывает у попарного слияния.
- «А без кучи?» — попарное слияние за тот же с памяти.
- «Найдите медиану всех элементов k списков» — для двух массивов это отдельная задача (медиана двух отсортированных массивов), для проще всего k-way merge до середины или бинпоиск по значению.
- «Верните k наибольших элементов» — это уже не слияние, а top-k через кучу или quickselect.
Чтобы отличить k-way merge от top-k, посмотрите на вход: если в нём несколько уже отсортированных последовательностей, и важен их порядок, — это k-way merge, куча размера по числу списков. Если вход — одна неупорядоченная куча данных и нужны лучших, — это top-k, куча размера по числу ответов.
Что запомнить
- K-way merge — это слияние двух списков, где выбор меньшей головы делегирован min-куче.
- В куче по одному кандидату от каждого источника, кортеж
(значение, номер источника, позиция). - времени, памяти; попарное слияние даёт ту же асимптотику без кучи.
- «Источником» может быть строка матрицы, правило генерации пар или файл на диске.
- Smallest Range — тот же k-way merge плюс текущий максимум; останавливаемся, когда кончился любой список.
- Внешняя сортировка: прогоны размером с память, затем слияние с максимальным числом входов, чтобы сократить проходы по диску.