Объединение потоков данных с использованием O (1) RAM

Question

Как объединить k отсортированных потоков данных с помощью O (1) RAM? Как определить объект потока данных и связанные с ним функции/операции?

Мое решение: Я думал о том, чтобы использовать списки массивов в качестве объекта потока данных. Я планировал найти минимальное значение 0-го индекса списка k-массивов. Минимальное значение должно быть удалено из этого списка массивов и должно быть помещено в список выходных массивов. Этот процесс должен быть повторен до тех пор, пока все списки массивов k не станут нулями. Но я предполагаю, что это займет O (k * длина каждого списка массивов). Любые идеи, как это сделать в O (1)?

Answer 1

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

http://en.wikipedia.org/wiki/Merge_sort

Функция слияния занимает O (1) памяти. Теперь все, что вам нужно, это индекс в ваш набор потоков данных и объединить все потоки в первый поток, и все готово.