Внешняя сортировка с кучей?

Использование пирамидальной сортировки требует множества операций поиска в файле для первоначального создания кучи, а также при удалении верхнего элемента. По этой причине это не очень хорошая идея.

Однако вы можете использовать разновидность сортировки слиянием, в которой каждый элемент кучи представляет собой отсортированный список. Размер списков определяется тем, сколько вы хотите сохранить в памяти. Вы создаете эти списки из входного файла с помощью загрузки фрагментов данных, их сортировки и последующей записи во временный файл. Затем вы обрабатываете каждый файл как один список, читаете первый элемент и создаете из него кучу. При удалении верхнего элемента вы удаляете его из списка и при необходимости восстанавливаете состояние кучи.

Однако есть один аспект, который делает эти факты о сортировке неуместными: вы говорите, что хотите определить первые 10 элементов. Для этого вы действительно можете использовать кучу в памяти. Просто возьмите элемент из файла, поместите его в кучу и, если размер кучи превышает 10, удалите самый младший элемент. Чтобы сделать его более эффективным, поместите его в кучу только в том случае, если размер меньше 10 или выше самого нижнего элемента, который вы затем заменяете и повторно кучаете. Хранение первой десятки в куче позволяет вам просканировать файл только один раз, все остальное будет сделано в памяти. Использование двоичного дерева вместо кучи также будет работать и, вероятно, будет таким же быстрым, для небольшого числа, такого как 10, вы даже можете использовать массив и пузырьковую сортировку элементов на месте.

Примечание. Я предполагаю, что 10 и 100 были просто примерами. Если ваши цифры действительно настолько малы, любые обсуждения эффективности, вероятно, спорны, если только вы не выполняете эту операцию несколько раз в секунду.

Да, вы можете использовать кучу для поиска элементов top-k в большом файле, удерживая в памяти только кучу + буфер ввода-вывода.

Следующее будет получать элементы min-k, используя максимальную кучу длины k. Вы можете читать файл последовательно, выполняя ввод-вывод для каждого элемента, но обычно намного быстрее загружать данные блоками во вспомогательный буфер длиной b. Метод выполняется в O(n*log(k)) операциях с использованием O(k + b) пространства.

while (file not empty)

    read block from file

    for (i = all items in block)
        if (heap.count() < k)
            heap.push(item[i])
        else
        if (item[i] < heap.root())
            heap.pop_root()
            heap.push(item[i])
        endif
    endfor

endwhile

Кучи требуют много непоследовательного доступа. Сортировка слиянием отлично подходит для внешней сортировки, потому что она выполняет много последовательного доступа.

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

Используя сортировку слиянием и передавая два значения reference вам нужно только удерживать два значения сравнения в буфере и перемещаться по массиву, пока он не будет отсортирован на месте.