Выбор лучших n элементов из нескольких отсортированных массивов

Question

Каков оптимальный алгоритм для выбора верхних n элементов из нескольких массивов, при условии, что каждый массив отсортирован таким же образом, каким должен быть результирующий массив.

Чтение элементов очень дорого, и поэтому количество операций чтения должно быть абсолютным минимумом.

Answer 1

Поместить кортежи (current_element, array_number, current_index=0) в приоритетную очередь (например, на основе двоичной max-heap), упорядоченную по значению элемента

Затем удалите верхнюю часть очереди n раз.

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