Алгоритмы с нуля

K-путевое слияние и слияние отсортированных списков

Суть Объедини k отсортированных списков: мин-куча с головой каждого, вытащи минимум, добавь в вывод, добавь следующий из того же списка. O(n log k) время, O(k) память. Лучше наивного O(nk).

◷ 36 min

У тебя есть k отсортированных списков. Задача: объединить их в один отсортированный список. Наивный ответ: сканируй голову всех k списков, найди наименьший, добавь его к выводу, двигайся вперёд. Повторяй до истощения. Но сканирование k голов за каждый шаг это O(nk) — медленно. Ключевое: держи мин-кучу размера k с головой каждого списка. Вытащи наименьшую голову, добавь её, добавь следующий элемент из того же списка. Куча держит k наименьших кандидатов на вершине, так что каждый вытаск/добавь это O(log k). Итоговое время: O(n log k). Память: O(k). Это паттерн k-путевого слияния.

Цель

После этого урока ты можешь решить проблему слияния k отсортированных списков используя мин-кучу: инициализируй кучу с головой каждого списка (отслеживая какой список каждая голова представляет), вытащи наименьший, добавь к выводу, и добавь следующий элемент из того же списка. Ты понимаешь почему это работает: куча всегда держит одного кандидата из каждого из k списков, и корень всегда это общий минимум в этот момент. Ты можешь объяснить сложность времени O(n log k) и сложность памяти O(k), и почему это бьёт наивный подход O(nk). Ты можешь узнать форму «объедини k отсортированных X» на LeetCode (связные списки, массивы, итераторы), отследить алгоритм шаг за шагом на конкретном вводе, и кодировать его. Ты понимаешь варианты наименьший-диапазон и объединение-отсортированных-массивов. Это твой финальный урок куч; дальше графы.

Идея

Проблема: объедини k отсортированных списков

Дано k отсортированных списков. Задача: объединить их в один отсортированный вывод список, сохраняя порядок.

Пример:

Списки: [1, 4, 5], [1, 3, 4], [2, 6]
Объединённо: [1, 1, 2, 3, 4, 4, 5, 6]

Наивный подход: сканируй все головы за каждый шаг

За каждый шаг:

Сканируй голову всех k списков чтобы найти минимум.
Добавь минимум к выводу.
Двигай указатель в том списке вперёд.

Время: O(n) шагов, и каждый шаг сканирует k голов в O(k). Итого: O(nk). Это медленно когда k большой.

Ключевое для кучи: держи кучу размера-k голов

Вместо сканирования всех k голов, используй мин-кучу их отслеживать. Вот алгоритм:

Создай мин-кучу.
Для каждого из k списков, добавь его голову (первый элемент) в кучу. Храни с каждой записью кучи индекс списка и текущую позицию в том списке, так ты знаешь какой список вытягивать следующим.
Пока куча не пуста:
- Вытащи минимум из кучи.
- Добавь его к выводу.
- Если тот список имеет следующий элемент, добавь его в кучу (тот же индекс списка, следующая позиция).
Вывод теперь объединённый и отсортированный.

Почему это работает? На любом шаге, куча держит ровно одного кандидата из каждого из k списков. Корень это общий минимум среди этих кандидатов. Когда ты вытаскиваешь его и добавляешь следующий элемент из того же списка, куча держит инвариант: всегда k наименьших кандидатов видимых до сих пор, один за список. Каждый вытаск/добавь это O(log k), и ты делаешь n итого вытасков, так O(n log k) всего.

Пример: объедини три списка [1, 4, 5], [1, 3, 4], [2, 6]

Мин-куча держит (значение, индекс_списка, позиция):

Инициализируй: добавь (1, список 0, поз 0), (1, список 1, поз 0), (2, список 2, поз 0). Куча: мин это (1, 0, 0).
Вытащи (1, 0, 0), добавь 1 к выводу. Добавь (4, 0, 1). Вывод: [1]. Куча мин: (1, 1, 0).
Вытащи (1, 1, 0), добавь 1. Добавь (3, 1, 1). Вывод: [1, 1]. Куча мин: (2, 2, 0).
Вытащи (2, 2, 0), добавь 2. Добавь (6, 2, 1). Вывод: [1, 1, 2]. Куча мин: (3, 1, 1).
Вытащи (3, 1, 1), добавь 3. Добавь (4, 1, 2). Вывод: [1, 1, 2, 3]. Куча мин: (4, 0, 1).
Вытащи (4, 0, 1), добавь 4. Добавь (5, 0, 2). Вывод: [1, 1, 2, 3, 4]. Куча мин: (4, 1, 2).
Вытащи (4, 1, 2), добавь 4. Список 1 истощен. Вывод: [1, 1, 2, 3, 4, 4]. Куча мин: (5, 0, 2).
Вытащи (5, 0, 2), добавь 5. Список 0 истощен. Вывод: [1, 1, 2, 3, 4, 4, 5]. Куча мин: (6, 2, 1).
Вытащи (6, 2, 1), добавь 6. Список 2 истощен. Вывод: [1, 1, 2, 3, 4, 4, 5, 6]. Куча пуста. Готово.

Финально: [1, 1, 2, 3, 4, 4, 5, 6]. ✓

Почему размер кучи остаётся при k

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

Флагманская форма: объедини k отсортированных связных списков

Частая проблема LeetCode: дано k отсортированных связных списков, объедини их. Алгоритм идентичен. Вместо массивов, ты пересекаешь указатели. Каждая запись кучи хранит узел, не просто значение. Ты вытаскиваешь мин узел, добавляешь его, и добавляешь его следующий узел.

Вариант: наименьший диапазон

Дано k массивов, найди наименьший диапазон что включает по крайней мере один элемент из каждого массива. Решение: используй подобную кучу отслеживать текущий элемент из каждого массива. Держи минимум и максимум текущих k элементов. Диапазон [мин, макс] это кандидат ответ. Вытащи мин и добавь следующий из того массива. Отслеживай наименьший диапазон видимый. Время: O(n log k).

Вариант: объедини отсортированные массивы (разные размеры)

k массивов разных размеров. Объедини их в O(n log k) время используя одинаковый подход куча. n = всего элементов через все массивы.

Код

Объединение k отсортированных массивов используя мин-кучу


      1
      function mergeKSortedLists(lists) {
    

      2
      // Мин-куча держит [значение, индекс_списка, позиция]
    

      3
      const minHeap = new MinPriorityQueue();
    

      4
      const result = [];
    

      5
       
    

      6
      // Добавь голову каждого списка
    

      7
      for (let i = 0; i < lists.length; i++) {
    

      8
        if (lists[i].length > 0) {
    

      9
          // Храни: значение, индекс списка, позиция в том списке
    

      10
          minHeap.insert([lists[i][0], i, 0], lists[i][0]);
    

      11
        }
    

      12
      }
    

      13
       
    

      14
      // Вытащи мин, добавь, добавь следующий из того же списка
    

      15
      while (!minHeap.isEmpty()) {
    

      16
        const [value, listIdx, pos] = minHeap.extractMin();
    

      17
        result.push(value);
    

      18
        
    

      19
        // Если есть следующий элемент в том списке, добавь его
    

      20
        if (pos + 1 < lists[listIdx].length) {
    

      21
          const nextValue = lists[listIdx][pos + 1];
    

      22
          minHeap.insert([nextValue, listIdx, pos + 1], nextValue);
    

      23
        }
    

      24
      }
    

      25
       
    

      26
      return result;
    

      27
      }
    

      28
       
    

      29
      // Пример
    

      30
      const lists = [[1, 4, 5], [1, 3, 4], [2, 6]];
    

      31
      const merged = mergeKSortedLists(lists);
    

      32
      console.log(merged); // [1, 1, 2, 3, 4, 4, 5, 6]

L2 Мин-куча где ключ это значение само. Каждая запись это [значение, индекс_списка, позиция].
L7 Для каждого из k списков, добавь первый элемент (если список не пуст).
L8 Храни значение, список откуда оно пришло, и его позицию в том списке.
L15 Пока куча не пуста, вытащи минимум значение (всегда в корне).
L19 Добавь к результату.
L22 Если тот же список имеет следующий элемент, добавь его. Если нет, тот список истощен.
L28 Вывод теперь объединённый и отсортированный.

Объедини k отсортированных связных списков

class Node {
constructor(val, next = null) {
  this.val = val;
  this.next = next;
}
}

class MinPriorityQueue {
constructor() {
  this.heap = [];
}

insert(item, priority) {
  this.heap.push(item);
  this.siftUp(this.heap.length - 1);
}

extractMin() {
  const root = this.heap[0];
  this.heap[0] = this.heap[this.heap.length - 1];
  this.heap.pop();
  if (this.heap.length > 0) {
    this.siftDown(0);
  }
  return root;
}

isEmpty() {
  return this.heap.length === 0;
}

siftUp(index) {
  while (index > 0) {
    const parentIdx = Math.floor((index - 1) / 2);
    if (this.heap[index][0] < this.heap[parentIdx][0]) {
      [this.heap[index], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[index]];
      index = parentIdx;
    } else {
      break;
    }
  }
}

siftDown(index) {
  while (true) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

if (left < this.heap.length && this.heap[left][0] < this.heap[smallest][0]) {
      smallest = left;
    }
    if (right < this.heap.length && this.heap[right][0] < this.heap[smallest][0]) {
      smallest = right;
    }

if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    } else {
      break;
    }
  }
}
}

function mergeKLinkedLists(lists) {
const minHeap = new MinPriorityQueue();

// Добавь голову каждого списка
for (let i = 0; i < lists.length; i++) {
  if (lists[i]) {
    // Храни: [узел, индекс_списка] с приоритет = узел.val
    minHeap.insert([lists[i], i]);
  }
}

const dummyHead = new Node(-1);
let current = dummyHead;

while (!minHeap.isEmpty()) {
  const [node, listIdx] = minHeap.extractMin();
  current.next = node;
  current = current.next;
  
  // Если этот узел имеет следующий, добавь его
  if (node.next) {
    minHeap.insert([node.next, listIdx]);
  }
}

return dummyHead.next;
}

// Пример: создай три связные списки
const list1 = new Node(1, new Node(4, new Node(5)));
const list2 = new Node(1, new Node(3, new Node(4)));
const list3 = new Node(2, new Node(6));

const merged = mergeKLinkedLists([list1, list2, list3]);

// Преобразуй в массив для отображения
const result = [];
let curr = merged;
while (curr) {
result.push(curr.val);
curr = curr.next;
}
console.log(result);

Output

Пошаговый разбор


      1
      const lists = [[1, 4, 5], [1, 3, 4], [2, 6]];
    

      2
      const minHeap = new MinPriorityQueue();
    

      3
      const result = [];
    

      4
      // Инициализируй: добавь головы всех списков
    

      5
      for (const [val, idx] of [[1,0], [1,1], [2,2]]) minHeap.insert(val, idx);
    

      6
      while (!minHeap.isEmpty()) {
    

      7
        const [val, idx] = minHeap.extractMin();
    

      8
        result.push(val);
    

      9
        if (hasNext(lists[idx])) minHeap.insert(nextVal(lists[idx]), idx);
    

      10
      }

Сложность

K-путевое слияние с мин-кучей размера k

У тебя есть n всего элементов через все k списков.

Для каждого из n элементов:

ExtractMin: O(log k) (куча держит максимум k элементов).
Insert (следующий элемент из того же списка): O(log k).

Итого: n элементов × (вытаск + добавь) = n × O(log k) = O(n log k) время.

Память: Куча держит максимум k элементов (одна голова из каждого списка), так O(k) память.

Сравнение с наивным подходом

Наивный: для каждого из n элементов, сканируй все k голов чтобы найти минимум. Время: O(nk). Память: O(1) (если ты не считаешь вход).

K-путевое слияние с кучей: O(n log k) время, O(k) память.

Когда подход кучи лучше?

Всегда. O(n log k) строго лучше чем O(nk), потому что log k ≤ n для разумного k (и обычно log k ≪ n).
Пример: n = 1,000,000 элементов, k = 100 списков. O(n log k) = 1,000,000 × 6.6 ≈ 6.6 миллионов операций. O(nk) = 1,000,000 × 100 = 100 миллионов операций. Куча ~15 раз быстрее.

Почему не другие подходы?

Попарное слияние (объедини два списка, потом объедини результат с третьим, и т.д.): O(n log k) но с большими константами. Куча проще.
Глобально отсортируй все элементы: O(n log n) время, O(n) память. Хуже чем O(n log k) когда k ≪ n.

Практика 0 / 6

Чтобы объединить k отсортированных списков, какая главная цель хранить индекс списка и позицию в каждой записи кучи?

В алгоритме k-путевого слияния, что гарантирует инвариант кучи на каждом шаге?

Ты объединяешь k = 5 отсортированных списков с n = 1,000,000 всего элементов. Какая приблизительная сложность времени в операциях, используя log₂(5) ≈ 2.3?

Какая сложность памяти алгоритма k-путевого слияния?

Дано три списка [1, 5, 9], [2, 6, 10], [3, 7, 11], что это первый элемент вытащен из мин-кучи?

После вытаскивания (1, L0) и добавления (5, L0) в предыдущем примере, что это следующий минимум вытащен?

lesson.inset.undefined

Почему k-путевое слияние имеет значение. Реальные системы часто нужно объединять отсортированные данные из множественных источников: объединение k файлов лога отсортированных по временам, объединение результатов из k шардов базы отсортированных по ID, объединение k отсортированных итераторов в конвейер данных. Ты не можешь себе позволить хранить все данные в памяти, так ты должен потоком пройтись через один элемент за раз. K-путевая куча позволяет тебе объединять онлайн в O(n log k) время и O(k) память, обрабатывая каждый элемент ровно раз.

lesson.inset.undefined

Хранение весь остающийся список вместо просто головы. Это соблазнительно хранить весь хвост списка в куче. Это тратит память и делает сравнения медленно. Вместо, храни только узел/значение само и его индекс списка/позицию. Когда ты вытаскиваешь его, ты вычисляешь или получаешь следующий элемент по требованию. Куча никогда не держит больше чем k элементов.

lesson.inset.undefined

Пустые списки. Если некоторые входные списки пусты, не добавляй их в кучу. Алгоритм правильно обрабатывает k-m непустых списков: размер кучи растёт к количеству непустых списков, и сложность O(n log (k-m)). Если все списки пусты, вывод пуст. Если k = 1, есть только один список, так просто верни его.

lesson.inset.undefined

Вариант наименьший-диапазон. Дано k массивов, найди наименьший диапазон [a, b] такой что каждый массив вносит по крайней мере один элемент. Держи текущий мин и макс среди k голов. Диапазон [мин, макс] это кандидат ответ. Вытащи мин, добавь следующий из того массива, обновить диапазон. Время: O(n log k). Память: O(k).

Проверь себя

Викторина

Объясни алгоритм k-путевого слияния и его сложность времени. Почему это O(n log k) и не O(nk)?

Итог

Чтобы объединить k отсортированных списков, держи мин-кучу размера k с одной головой из каждого списка. Вытащи минимум голову, добавь её к выводу, добавь следующий элемент из того же списка. Инвариант кучи гарантирует корень это всегда минимум среди k текущих голов. Время: O(n log k). Память: O(k). Это намного лучше чем наивный подход O(nk) (сканирование всех k голов за шаг). Одинаковый паттерн решает объединение k отсортированных связных списков, наименьший-диапазон, и объединение k отсортированных массивов. Следующее: модуль 09 (графы), где ты будешь исследовать узлы и рёбра, BFS, DFS, и кратчайшие пути.

Продолжить восхождение ↑Heap: тест с выбором ответа