K-way merge: слияние k отсортированных списков через кучу

Паттерн K-way merge на примерах: Merge k Sorted Lists, k-й наименьший в отсортированной матрице, Smallest Range Covering k Lists и внешняя сортировка. Куча на k элементов, код на Python.

15 мин чтенияалгоритмы · кучи · python

Коротко

ЗадачаРешениеВремяПамять
Слить k отсортированных массивовmin-куча из «голов»O(Nlog⁡k)O(N \log k)O(k)O(k) + ответ
Merge k Sorted Lists (LeetCode 23)куча или попарное слияниеO(Nlog⁡k)O(N \log k)O(k)O(k) / O(1)O(1)
k-й наименьший в матрице (LC 378)куча по строкам или бинпоиск по ответуO(klog⁡n)O(k \log n) / O(nlog⁡V)O(n \log V)O(n)O(n) / O(1)O(1)
Smallest Range Covering k Lists (LC 632)куча + текущий максимумO(Nlog⁡k)O(N \log k)O(k)O(k)
Внешняя сортировкаотсортированные прогоны + k-way mergeO(Nlog⁡N)O(N \log N), мало проходов по дискуO(M)O(M)

Здесь NN — общее число элементов, kk — число списков.

  • В куче лежит ровно по одному кандидату от каждого списка — его текущая «голова». Достали минимум, положили следующий элемент из того же списка.
  • Куча размера kk даёт O(log⁡k)O(\log k) на шаг вместо O(k)O(k) на линейный поиск минимума.
  • В кортеже для кучи всегда держите индекс списка: он разруливает равные значения и не даёт Python сравнивать узлы.
  • Паттерн узнаётся по фразе «даны несколько отсортированных последовательностей» — даже если они спрятаны в строках матрицы или генерируются на лету.

Откуда паттерн и как его узнать

Слияние двух отсортированных списков — база, её подробно разбирает статья про объединение двух отсортированных списков: два указателя, на каждом шаге берём меньшую голову. K-way merge обобщает это на kk источников.

С двумя указателями выбрать меньшую голову — одно сравнение. С kk указателями наивный выбор стоит O(k)O(k), и при NN элементах получаем O(N⋅k)O(N \cdot k). Нужна структура, которая хранит kk голов и быстро отдаёт минимальную, — это min-куча, она же приоритетная очередь. Как куча устроена внутри, описано в статье про бинарную кучу; здесь нам хватит heapq.

Признаки задачи на k-way merge:

  • на входе kk отсортированных массивов, списков, файлов, потоков;
  • есть матрица, где отсортированы строки (или строки и столбцы), и спрашивают про порядок элементов;
  • спрашивают «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)14 из #0
2(3,2) (4,0) (5,1)25 из #1
3(4,0) (5,1) (6,2)36 из #2
4(5,1) (6,2) (7,0)47 из #0
5(6,2) (7,0)5#1 пуст

Инвариант: в куче не больше одного элемента от каждого массива, и это наименьший ещё не выведенный элемент своего массива. Значит, минимум кучи — минимум среди всего, что осталось. Отсюда корректность.

Сложность. Каждый из NN элементов один раз попадает в кучу и один раз из неё уходит: O(Nlog⁡k)O(N \log k). heapify на старте — O(k)O(k). Память — O(k)O(k) на кучу плюс сам ответ.

Готовое в стандартной библиотеке

В 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. Даны kk отсортированных односвязных списков, нужно слить их в один.

Вход: [1→4→5, 1→3→4, 2→6] Выход: 1→1→2→3→4→4→5→6

Наивные решения

Собрать всё и отсортировать. Пройти списки, сложить значения в массив, sort(), собрать новый список. O(Nlog⁡N)O(N \log N) по времени и O(N)O(N) по памяти. Работает, но не использует то, что списки уже отсортированы, — интервьюер спросит, можно ли лучше.

Сливать по одному. result = merge(result, lists[i]) в цикле. Выглядит естественно, но result растёт: на ii-м шаге он длиной около i⋅ni \cdot n, где nn — длина одного списка. Сумма даёт O(k2n)=O(k⋅N)O(k^2 n) = O(k \cdot N). При k=104k = 10^4 это уже медленно.

Решение через кучу

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]

Уровней слияния ⌈log⁡2k⌉\lceil \log_2 k \rceil, на каждом уровне все NN узлов проходят через merge_two один раз — итого тот же O(Nlog⁡k)O(N \log k). Зато нет кучи: дополнительная память O(1)O(1) (итеративная версия, без рекурсии), и константа обычно меньше.

ПодходВремяДоп. памятьКогда выбрать
Собрать и отсортироватьO(Nlog⁡N)O(N \log N)O(N)O(N)быстрый прототип, kk сравнимо с NN
По одномуO(k⋅N)O(k \cdot N)O(1)O(1)никогда, кроме k≤3k \le 3
КучаO(Nlog⁡k)O(N \log k)O(k)O(k)данные приходят потоком, списки разной длины
Попарное слияниеO(Nlog⁡k)O(N \log k)O(1)O(1)все списки уже в памяти

Важное отличие: куча работает со стримами. Ей не нужно знать списки целиком — достаточно уметь брать следующий элемент. Попарное слияние требует, чтобы все входы были доступны сразу. На этом построена внешняя сортировка, о ней ниже.

k-й наименьший элемент в отсортированной матрице

LeetCode 378, Medium. Матрица n×nn \times n, каждая строка и каждый столбец отсортированы по возрастанию. Найти kk-й наименьший элемент (с учётом повторов).

matrix = [[ 1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8 → 13

Отсортированный порядок: 1, 5, 9, 10, 11, 12, 13, 13, 15.

Решение через кучу

Каждая строка — отсортированный список. Значит, перед нами задача «слить nn списков», только всё слияние не нужно: достаточно остановиться на kk-м шаге.

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

Выбрасываем из кучи k−1k - 1 минимум, и на вершине остаётся ответ. Время O(min⁡(n,k)+klog⁡min⁡(n,k))O(\min(n, k) + k \log \min(n, k)), память O(min⁡(n,k))O(\min(n, k)).

Отсортированность столбцов здесь использована лишь слегка — в отсечении строк дальше kk-й. Для этого решения хватило бы и отсортированных строк.

Бинарный поиск по значению

Когда kk порядка n2n^2, куча делает O(n2log⁡n)O(n^2 \log n) — почти как полная сортировка. Сортированные столбцы позволяют лучше: бинарный поиск по ответу. Ищем наименьшее значение xx, для которого элементов ≤x\le x не меньше kk.

Сколько элементов ≤x\le x, считается за O(n)O(n) «лесенкой»: идём по строкам сверху вниз, а указатель столбца двигаем только влево — в следующей строке все элементы не меньше, чем в предыдущей, поэтому граница не сдвигается вправо.

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

Время O(nlog⁡V)O(n \log V), где VV — разность максимума и минимума, память O(1)O(1). Почему ответ — обязательно элемент матрицы, хотя мы перебираем произвольные числа: lo — наименьшее xx с count_le(x) >= k, а при xx между двумя соседними значениями матрицы счётчик не меняется. Значит, минимальное такое xx совпадает с каким-то элементом.

На собеседовании хорошо рассказать оба варианта: куча — как прямое применение k-way merge, бинпоиск — как оптимизация при больших kk.

Родственная задача: k пар с наименьшими суммами

LeetCode 373: даны два отсортированных массива, вернуть kk пар (ai,bj)(a_i, b_j) с наименьшими суммами. Это та же матрица в неявном виде: строка ii — суммы nums1[i] + nums2[j] по всем jj, и она отсортирована. Строить матрицу не нужно, элементы считаются на лету.

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]]

O(klog⁡min⁡(k,m))O(k \log \min(k, m)), где mm — длина nums1. Это частый приём: «списки» в k-way merge могут быть не данными, а правилом генерации следующего кандидата.

Smallest Range Covering Elements from K Lists

LeetCode 632, Hard. Даны kk отсортированных списков. Найти наименьший диапазон [a,b][a, b], в который попадает хотя бы по одному числу из каждого списка. При равной длине выбирается диапазон с меньшим aa.

[[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]

Пройдём пример по шагам (в скобках — головы трёх списков):

ГоловыminmaxДиапазонЛучший
(4, 0, 5)05[0, 5][0, 5]
(4, 9, 5)49[4, 9][0, 5]
(10, 9, 5)510[5, 10][0, 5]
(10, 9, 18)918[9, 18][0, 5]
(10, 12, 18)1018[10, 18][0, 5]
(15, 12, 18)1218[12, 18][0, 5]
(15, 20, 18)1520[15, 20][0, 5]
(24, 20, 18)1824[18, 24][0, 5]
(24, 20, 22)2024[20, 24][20, 24]

Диапазоны той же длины 5 ([4, 9], [5, 10], [15, 20]) лучший не заменяют — работает строгое <. После последней строки минимум 20 уходит из кучи, а следующего элемента во втором списке нет — выходим с ответом [20, 24].

Почему останавливаемся, когда кончился один список. Минимум набора — последний элемент списка ii. Чтобы получить новый диапазон, нужно поднять минимум, то есть заменить этот элемент следующим из списка ii, — а его нет. Любой диапазон с началом правее этого элемента вообще не покрывает список ii, так что проверять больше нечего.

Сложность. O(Nlog⁡k)O(N \log k) по времени, O(k)O(k) по памяти. Строгое < при сравнении длины гарантирует, что при равенстве останется диапазон с меньшим началом: минимумы мы перебираем по возрастанию.

Есть и альтернатива без кучи: слить все элементы в один массив пар (значение, номер списка), отсортировать и найти минимальное окно, где встречаются все kk номеров, — классическое скользящее окно. Это O(Nlog⁡N)O(N \log N) и O(N)O(N) памяти — проще доказать, но тяжелее по ресурсам.

Внешняя сортировка

Главное «промышленное» применение k-way merge. Задача: отсортировать файл, который не помещается в оперативную память. Скажем, 100 ГБ чисел при 2 ГБ памяти. Такое спрашивают и на алгоритмической секции, и на системном дизайне («отсортируй логи за месяц», «найди дубликаты в огромном файле»).

Двухфазный алгоритм

  1. Фаза прогонов (runs). Читаем вход кусками размером с доступную память, каждый кусок сортируем обычной сортировкой и пишем на диск отдельным файлом. Получаем k=⌈100/2⌉=50k = \lceil 100 / 2 \rceil = 50 отсортированных файлов.
  2. Фаза слияния. Открываем все 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)

Во второй фазе в памяти одновременно живут только kk голов плюс буферы открытых файлов — объём исходного файла здесь роли не играет. Python буферизует чтение сам; в реальной системе размер буферов подбирают явно.

Что спросят дальше

Сколько файлов можно слить за раз? Каждому входу нужен буфер, иначе чтение превратится в случайные мелкие обращения к диску. При памяти MM и буфере BB сливаем до M/B−1M / B - 1 файлов (один буфер — на выход). 2 ГБ и буфер 32 МБ дают около 60 входов. Если прогонов больше, слияние делают в несколько проходов: число проходов — ⌈log⁡fk⌉\lceil \log_{f} k \rceil, где ff — сколько файлов сливаем за раз. Поэтому выгодно делать ff большим: это и есть смысл k-way вместо попарного слияния. Попарное на 1000 прогонов — 10 проходов по всем данным, слияние по 99 — 2 прохода.

Как получить меньше прогонов? Алгоритм replacement selection: вместо «прочитал кусок — отсортировал» держим кучу размером с память, выводим из неё минимум и на его место читаем следующий элемент входа. Если новый элемент меньше только что выведенного, в текущий прогон он уже не попадёт — его откладывают в следующий. Прогон заканчивается, когда в куче остались только отложенные. На случайных данных прогоны получаются в среднем вдвое длиннее памяти, на почти отсортированных — гораздо длиннее.

Чем заменить кучу? В СУБД и библиотеках внешней сортировки часто используют турнирное дерево проигравших (loser tree): после извлечения минимума оно делает ровно ⌈log⁡2k⌉\lceil \log_2 k \rceil сравнений по пути от листа к корню, а куче при просеивании вниз нужно примерно вдвое больше — по два сравнения на уровень. Асимптотика та же.

Где это живёт в реальности. Внешняя сортировка в СУБД (сортировки и 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: O(Nlog⁡N)O(N \log N) времени и O(N)O(N) памяти. Смысл паттерна — куча размера kk.
  • Забыли положить следующий элемент. После heappop нужно добавить следующий элемент того же списка, а не любого. Иначе нарушается инвариант «по одному от каждого».
  • Сравнили с наивным неправильно. Слияние по одному — не O(Nlog⁡k)O(N \log k), а O(k⋅N)O(k \cdot N). Интервьюеры любят просить оценить именно его.
  • В Smallest Range обновляют максимум не там. current_max растёт только при добавлении нового элемента и никогда не уменьшается: вытолкнутый минимум на максимум не влияет.
  • В матрице берут k строк, когда строк меньше. range(min(n, k)), а не range(k).

Где встречается на собеседованиях

Merge k Sorted Lists — одна из самых известных Hard-задач, она есть почти в любом списке «топ задач для собеседования». Обычно её дают после разминки на слияние двух списков и смотрят, предложит ли кандидат кучу сам и сумеет ли оценить наивный вариант.

Типичные продолжения:

  • «А если списки не помещаются в память / приходят по сети?» — переход к внешней сортировке и стримингу, куча здесь выигрывает у попарного слияния.
  • «А без кучи?» — попарное слияние за тот же O(Nlog⁡k)O(N \log k) с O(1)O(1) памяти.
  • «Найдите медиану всех элементов k списков» — для двух массивов это отдельная задача (медиана двух отсортированных массивов), для kk проще всего k-way merge до середины или бинпоиск по значению.
  • «Верните k наибольших элементов» — это уже не слияние, а top-k через кучу или quickselect.

Чтобы отличить k-way merge от top-k, посмотрите на вход: если в нём несколько уже отсортированных последовательностей, и важен их порядок, — это k-way merge, куча размера kk по числу списков. Если вход — одна неупорядоченная куча данных и нужны kk лучших, — это top-k, куча размера kk по числу ответов.

Что запомнить

  • K-way merge — это слияние двух списков, где выбор меньшей головы делегирован min-куче.
  • В куче по одному кандидату от каждого источника, кортеж (значение, номер источника, позиция).
  • O(Nlog⁡k)O(N \log k) времени, O(k)O(k) памяти; попарное слияние даёт ту же асимптотику без кучи.
  • «Источником» может быть строка матрицы, правило генерации пар или файл на диске.
  • Smallest Range — тот же k-way merge плюс текущий максимум; останавливаемся, когда кончился любой список.
  • Внешняя сортировка: прогоны размером с память, затем слияние с максимальным числом входов, чтобы сократить проходы по диску.

Потренироваться в спокойной обстановке

Все задачи