Блог

нам было предоставлено k отсортированных массивов. Допустим, k =3 a1={1,4,7} a2={3,5} a3={2,6,7} теперь мы должны объединить эти 3 массива в отсортированном порядке. Следовательно, результат будет {1,2,3,4,5,6,7,7}. Теперь в учебнике, которому я следую, они сохранили индекс и использовали пары для решения этого вопроса, используя минимальные кучи. Но мой вопрос в том, что, поскольку min heaps хранит элементы в отсортированном порядке, можем ли мы просто использовать функцию push min heap для всех элементов из k массивов, а затем в конце распечатать минимальную кучу?? вместо того, чтобы хранить индекс и создавать пары? в c ?

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

Я предполагаю, что данное решение состоит в том, чтобы построить k «итераторы» в массивы, поместить их в кучу, отсортированную по значению на каждом итераторе, а затем повторно удалить наименьший итератор, использовать его значение, увеличить его и поместить обратно в кучу. Ключ в том, что куча (в которой происходит вся работа) меньше: она содержит только k элементы вместо k*n . Это делает каждую операцию с кучей быстрее: теперь операции с кучей в этом алгоритме выполняются O(log k) . Общий алгоритм теперь O(k*n*log k) улучшен.

Я думаю, что этот алгоритм-то, что вы ищете.:

Создайте минимальную кучу и вставьте первый элемент из всех k массивов. Выполните цикл, пока размер горной кучи не станет больше нуля. Удалите верхний элемент стопки и распечатайте его. Теперь вставьте следующий элемент из того же массива, к которому принадлежал удаленный элемент. Если в массиве больше нет элементов, замените корневой на бесконечный.После замены корня сложите дерево в кучу.

И о необходимом времени: O( n * k * log k), для вставки и удаления в минимальной куче требуется время журнала k. Таким образом, общая трудоемкость составляет O( n * k * log k)

Но мой вопрос в том, что, поскольку min heaps хранит элементы в отсортированном порядке, можем ли мы просто использовать функцию push min heap для всех элементов из k массивов, а затем в конце распечатать минимальную кучу??

Основное рекурсивное правило для минимальной кучи: левый и правый дочерний элемент должны быть меньше родительского. Это не означает, что левый ребенок должен быть меньше, чем родитель правой стороны дерева. Прикрепленное изображение показывает минимальную кучу. Но эта минимальная куча не является окончательно отсортированным массивом