Объединение K отсортированных списков: эффективность

Question

Я получил домашнее задание, которое требует от меня эффективного объединения отсортированных списков K, содержащих всего N элементов, в один отсортированный список. Методы, на которые я наткнулся, - это использовать минимальную кучу для сортировки элементов из списков K или использовать подход «разделяй и властвуй» (попарное слияние). Комментарии в этой теме говорят о том, что подход «Разделяй и властвуй» требует временной сложности O (NK), тогда как минимальная куча принимает O (N log K), и обе имеют одинаковую пространственную сложность. Я также посетил много других тем, но я не могу получить ясную картину.

Сомнения и вопросы:

1. На многих других сайтах говорилось, что подход «Разделяй и властвуй» и «Мин-куча» имеет временную сложность O (N log K). Это правда или ложь?
2. Пространственная сложность обоих подходов одинакова? Если нет, чем они отличаются?
3. Почему, если подход Min-heap лучше, чем Divide & Conquer для списков различной длины?
4. Я также обнаружил, что вы можете использовать Приоритетную очередь для решения проблема. Как это соотносится с этим?

Answer 1

Этот поток о K пути слияния. Это то, что вы смотрите на первое значение всех K списков, затем берете один элемент из одного списка и повторяете.

Настало время O(n K), потому что для каждого из n элементов, которые вы ищете для минимума K списков.

Разделение и объединение занимает O(n) для одного набора слияний, что сокращает количество списков пополам. Таким образом, после слияния log(K) вы выполняете время O(n log(K)).

Мин-куча похожа на слияние K, за исключением того, что для поиска наименьшего элемента требуется только время O(1) O(log(K)) чтобы получить это. Так что требуется время O(n log(K)).

Мин-куча - это реализация очереди приоритетов, поэтому она одинакова.

Все эти методы занимают одинаковое пространство, O(n) .

Удачи в кодировании, какой бы вы ни выбрали!