#algorithm
#алгоритм
Вопрос:
В многоходовом слиянии задача состоит в том, чтобы найти наименьший элемент из k элементов
Решение: приоритетные очереди
Идея: возьмите наименьшие элементы из первых k запусков, сохраните их в основной памяти в дереве кучи.
Затем повторно выводите наименьший элемент из кучи. Наименьший элемент заменяется следующим элементом из прогона, из которого он был получен.
Когда закончите с первым набором запусков, проделайте то же самое со следующим набором запусков.
Предположим, что размер моей основной памяти (M) меньше k, как мы можем сортировать элементы, другими словами, как работает многоходовой алгоритм слияния merge, если размер памяти M меньше K
Например, если у меня M = 3 и у меня есть следующее
Tape1: 8 9 10 Tape2: 11 12 13 Tape3: 14 15 16 Tape4: 45 6
Мой вопрос, как будет работать многоходовое слияние, потому что мы будем считывать 8, 11, 14 и выстраивать очередь приоритетов, мы помещаем 8 на выходную ленту, а затем пересылаем Tape1, я не понимаю, когда Tape4 считывается и как мы будем сравнивать с уже записанным на выходную ленту?
Спасибо!
Ответ №1:
Это не сработает. Вы должны выбрать k достаточно маленький для доступной памяти.
В этом случае вы могли бы выполнить 3-полосное слияние первых 3 лент, а затем 2-полосное слияние между результатом этого и одной оставшейся лентой. Или вы могли бы выполнить 3 2-полосных слияния (две пары лент, затем объединить результаты), что проще реализовать, но обеспечивает больший доступ к ленте.
Теоретически вы могли бы отказаться от приоритетной очереди. Тогда вам не нужно было бы хранить k элементы в памяти, но вам часто приходилось бы просматривать следующий элемент на всех k лентах, чтобы найти наименьший.