Объединение нескольких массивов с использованием двоичной кучи

Question

Учитывая k отсортированных массивов целых чисел, каждый из которых содержит неизвестное положительное количество элементов (необязательно одинаковое количество элементов в каждом массиве), где общее количество элементов во всех k массивах равно n, дать алгоритм для объединения k массивов в один отсортированный массив, содержащий все n элементов. Временная сложность алгоритма в худшем случае должна быть O (n ∙ log k).

Answer 1

Назовите k-отсортированные списки 1, ..., k.

Пусть A будет именем объединенного отсортированного массива.

Для каждого списка i, pop v от i и нажмите (i, v) в минимальную кучу.Теперь куча будет содержать пары значений и идентификатора списка для наименьших записей в каждом из списков.

Пока куча не пуста, вытолкните (i, v) из кучи и добавьте v к A,Вытащите следующий элемент из списка i (если он не пустой) и поместите его в кучу.

В куче есть n добавлений и удалений.Куча содержит не более k элементов на каждом временном шаге.Следовательно, время выполнения составляет O(n log k).

Answer 2

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