Рассмотрим двоичную максимальную кучу с n
элементами. Он будет иметь высоту O(log n)
. Когда новые элементы вставляются в кучу, они будут распространяться в куче, так что всегда выполняется свойство max-heap.
Новый элемент будет добавлен как дочерний на последнем уровне. Но после вставки может быть нарушение свойства max-heap. Следовательно, будет использоваться метод heapify. Это будет иметь временную сложность O(log n)
, то есть высоту кучи.
Но можем ли мы сделать его еще эффективнее?
Когда выполняется несколько операций вставки и удаления, эта процедура замедляет работу. Кроме того, существует строгое требование, чтобы куча была максимальной после каждой вставки.
Цель состоит в том, чтобы уменьшить временную сложность метода heapify. Это возможно только при уменьшении количества сравнений.
Если вы говорите о сложности алгоритма, нет возможности сделать вставку/удаление быстрее, потому что на данный момент сложность сортировки (путем сравнения) произвольного массива составляет O (nlogn), и если вы нашли способ быстрее, это будет противоречит этому.. если вы говорите об эффективности компьютера (более быстрый алгоритм с константой), это зависит от многих переменных, таких как язык кода/процессор/потоки и т. д. в любом случае, нет более быстрого способа, если вы говорите о сложности вставки/ удаление с произвольным массивом.
@AbhinavMathur Выполняя heapify, я обнаружил, что элементы на пути от нового листового узла, вставленного в кучу, до корневого узла всегда будут иметь элементы, отсортированные в порядке возрастания, идущие вверх. Следовательно, можно было бы каким-то образом определить точную позицию для размещения нового узла. Это как сначала выполнить поиск (чтобы определить точную позицию, в которую будет вставлен новый узел, а затем просто вставить его в эту точку). Это может помочь уменьшить количество сравнений, и не будет никакого распространения узла (что обычно происходит в методе heapify)
Хотя вы можете представить, что у вас будет меньше сравнений, у вас все равно будет такое же количество записей в вашем дереве (перемещение значений в другое место). Вы не можете уменьшить временную сложность. Разница между кучей до вставки и после вставки составляет O (logn).
@trincot Если используется бинарный поиск, не уменьшится ли общее количество сравнений? Предполагая, что мы используем массив для представления кучи.
Да, но это не помогает. После сравнения вам все равно придется перемещать значения, а их O (logn).
Но раньше было O(log n) сравнений. Но теперь, после выполнения бинарного поиска, выполняется O(log log n) сравнений. Это верно ? Разве нельзя сказать, что это улучшение?
Это было бы возможно с некоторыми дополнительными накладными расходами, но ваш вопрос (выделенный жирным шрифтом) гласит: «Цель состоит в том, чтобы уменьшить временную сложность метода heapify», чего не произойдет.
Да, это правильно. Но я также упомянул, что This is possible only when the number of comparisons are reduced.
Это неправильно?
Это действительно необходимое условие, но не достаточное.
post insertion, there can be violation of max-heap property. Hence, heapify method will be used
Я думаю, что heapify чаще используется как название для преобразования массива n элементов в кучу - известный алгоритм O (n). Операции по восстановлению свойства кучи после добавления элемента чаще называются просеиванием и завершением вставки.
Временная сложность операции вставки в кучу зависит от количества выполненных сравнений. Можно представить себе использование некоторых накладных расходов для реализации интеллектуального бинарного поиска по пути от листа к корню.
Однако временная сложность определяется не только количеством сравнений. Временная сложность определяется любой работой, которую необходимо выполнить, и в этом случае количество операций записи также равно O(log𝑛), и это количество операций записи нельзя уменьшить.
Количество узлов, значение которых необходимо изменить операцией вставки, равно O(log𝑛). Уменьшения количества сравнений недостаточно для снижения сложности.
If [o(log𝑛) heap insert] were possible, then heap sort would have become an algorithm with better complexity than O(𝑛log𝑛)
Нет. Все равно будет извлечение кучи O(log𝑛).
Да, я молча предположил, что (заявленная) оптимизация всплытия также применима к просеиванию. Если это утверждение не связано с улучшением, аналогичным просеиванию, то сложность сортировки кучи не улучшается.
Цель состоит в том, чтобы уменьшить временную сложность метода
heapify
.
Жаль, потому что это невозможно, в отличие от
Уменьшите временную сложность нескольких вставок и удалений:
Представьте, что вы не сразу вставляете в кучу n элементов,
построение вспомогательного (или даже списка).
При удалении (извлечении?) поместите один элемент из вспомогательного (теперь размером k) «в пустое место» и выполните просеивание вниз или вверх по мере необходимости, если k << n.
Если вспомогательная структура данных не намного меньше основной, объедините их.
Такие размышления приводят к продвинутым кучам вроде Фибоначчи, спаривания, Бродала…
«Но можем ли мы сделать его еще более эффективным?» Я уверен, что многие люди подумали бы о том, чтобы сделать его более эффективным, но это открытый вопрос. Вы думали о каком-либо способе сделать это?