Как объединить отсортированные списки в один список в O (n * log (k))

Question

(я получил это как вопрос для интервью и хотел бы помочь с этим.)

У вас есть k отсортированных списков, содержащих n разных номеров в общей сложности.
Показать, как создать один отсортированный список, содержащий все элементы из списков k в O(n * log(k))

Answer 1

Когда N=2, вы объединяете два списка, итеративно выдвигая переднюю часть списка, который является наименьшим.Таким образом, вы создаете виртуальный список, который поддерживает операцию pop_front, реализованную как:

pop_front(a, b): return if front(a) <= front(b) then pop_front(a) else pop_front(b)

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

pop_front(a, b, c, d): return if front(a, b) <= front(c, d) then pop_front(a, b) else pop_front(c, d)

Каждый поп будет включать каждый уровень в дереве один раз, что приводит к стоимости O(Log k) за поп.

---

Приведенные выше рассуждения неверны, поскольку они не учитываютfront операции, которые включают сравнение между двумя элементами, которые будут каскадно и, в конечном итоге, потребуют всего k-1 сравнений на выходной элемент.

Это можно обойти, "запоминая" передний элемент, т.е. сохраняяэто рядом с двумя списками после сравнения.Затем, когда элемент извлекается, этот передний элемент обновляется.

Это напрямую ведет к двоичному устройству минимальной кучи, как предлагает @ trincot.

    5 7 32 21
  5
    6 4 8 23 40
2
    7 7 20 53
  2
    2 4 6 8 10

Answer 2

Поскольку вопрос сформулирован, нет необходимости в k-way слиянии (или куче).Стандартное двухстороннее объединение, используемое повторно для объединения пар списков в любом порядке, пока не будет создан один отсортированный список, также будет иметь сложность по времени O (n log (k)).Если бы вместо этого был задан вопрос о том, как объединить k списков за один проход, тогда потребуется k-way merge.

Рассмотрим случай для k == 32, а для упрощения математики предположим, что все спискиобъединяются по порядку, так что каждый проход объединения объединяет все n элементов.После первого прохода есть k / 2 списков, после 2-го прохода, k / 4 списков, после log2 (k) = 5 проходов все k (32) списков объединяются в один отсортированный список.Помимо упрощения математики, порядок объединения списков не имеет значения, сложность времени при O (n log2 (k)) остается той же.

Использование k-way merge обычно выгодно толькопри объединении данных с использованием внешнего устройства, такого как один или несколько дисководов (или ленточные накопители классического использования), когда время ввода-вывода достаточно велико, чтобы можно было игнорировать издержки кучи.Для оперативной сортировки слиянием / слиянием общее число операций примерно одинаково для двухсторонней сортировки слияния / слияния или сортировки слиянием / слиянием k-way.На процессоре с 16 регистрами, большинство из которых используются в качестве индексов или указателей, оптимизированное (без кучи) четырехстороннее слияние (использование 8 регистров в качестве индексов или указателей на текущее и конечное местоположение каждого прогона) может быть немного быстреечем двухстороннее слияние из-за большей дружественности к кешу.

Answer 3

Идея состоит в том, чтобы использовать минимальную кучу размера k .

Вставить все списки k в кучу (одну кучу).-вход в список), вводятся по их минимальному (т.е. первому) значению

Затем многократно делают это:

1. Извлекают верхний список (имеющий минимальный ключ) из кучи
2. Извлеките минимальное значение из этого списка и поместите его в список результатов.
3. Переместите сокращенный список обратно (если он не пустой) в кучу, теперь введите новое минимальное значение

Повторяйте, пока все значения не будут помещены в список результатов.

Начальный шаг будет иметь временную сложность O (klogk) .

3 вышеуказанных шага будут повторяться n раз.На каждой итерации стоимость каждой составляет:

1. O (1)
2. O (1) , если извлечение выполняется с использованиемуказатель / индекс (не сдвигая все значения в списке)
3. O (log k) , поскольку размер кучи никогда не превышает k

Так чторезультирующая сложность составляет O (nlogk) (при k <<em> n , начальный шаг не имеет значения).