Как уменьшить сложность объединения нескольких массивов с помощью кучи?

Question

Я закодировал идею, представленную в этом вопросе: объединение отсортированных массивов, как можно увидеть здесь: расчет сложности Big-O для функции слияния и сортировки.

Как видно, сложность этого подхода больше, чем желательно. Есть ли лучший подход (кроме использования LINQ)? Каков основной недостаток этого подхода, если таковой имеется?

Answer 1

Мы можем объединить массивы за O(nk*Logk), используя Min Heap.

n= максимальный размер массива, k = количество массивов.

1. Создайте выходной массив размера n*k (вы можете просто распечатать их также).
2. Создайте минимальную кучу размера k и вставьте 1-й элемент во всех массивах в кучу
3. Повторите следующие шаги n*k раз.
   a) Получить минимальный элемент из кучи (минимум всегда в корне) и сохранить его в выходном массиве (или распечатать его).
   б) Замените корень кучи следующим элементом из массива, из которого этот элемент извлечен. Если в массиве больше нет элементов, замените корень на бесконечный. Заменив рут, поменяйте дерево.

Сложность времени: основной шаг 3rd шаг, цикл работает n*k раз. В каждой итерации цикла мы вызываем heapify, который принимает O(Logk) время.
Следовательно, сложность времени O(nk*Logk),

EDIT1: Heapify гарантирует, что у вас всегда есть min-heap, он меняет минимум дочерних узлов на родительский, если этот минимум меньше родительского.

Это гарантирует, что INFINITY элементы останутся внизу, а минимальный элемент из всех k массивы остаются вверху (корень) кучи.