Эффективный метод HEAPIFY для уменьшения количества сравнений

Рассмотрим двоичную максимальную кучу с n элементами. Он будет иметь высоту O(log n). Когда новые элементы вставляются в кучу, они будут распространяться в куче, так что всегда выполняется свойство max-heap.

Новый элемент будет добавлен как дочерний на последнем уровне. Но после вставки может быть нарушение свойства max-heap. Следовательно, будет использоваться метод heapify. Это будет иметь временную сложность O(log n), то есть высоту кучи.

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

Цель состоит в том, чтобы уменьшить временную сложность метода heapify. Это возможно только при уменьшении количества сравнений.

«Но можем ли мы сделать его еще более эффективным?» Я уверен, что многие люди подумали бы о том, чтобы сделать его более эффективным, но это открытый вопрос. Вы думали о каком-либо способе сделать это?

Abhinav Mathur 08.01.2023 06:52

Если вы говорите о сложности алгоритма, нет возможности сделать вставку/удаление быстрее, потому что на данный момент сложность сортировки (путем сравнения) произвольного массива составляет O (nlogn), и если вы нашли способ быстрее, это будет противоречит этому.. если вы говорите об эффективности компьютера (более быстрый алгоритм с константой), это зависит от многих переменных, таких как язык кода/процессор/потоки и т. д. в любом случае, нет более быстрого способа, если вы говорите о сложности вставки/ удаление с произвольным массивом.

JackRaBeat 08.01.2023 08:20

@AbhinavMathur Выполняя heapify, я обнаружил, что элементы на пути от нового листового узла, вставленного в кучу, до корневого узла всегда будут иметь элементы, отсортированные в порядке возрастания, идущие вверх. Следовательно, можно было бы каким-то образом определить точную позицию для размещения нового узла. Это как сначала выполнить поиск (чтобы определить точную позицию, в которую будет вставлен новый узел, а затем просто вставить его в эту точку). Это может помочь уменьшить количество сравнений, и не будет никакого распространения узла (что обычно происходит в методе heapify)

taurus05 08.01.2023 09:23

Хотя вы можете представить, что у вас будет меньше сравнений, у вас все равно будет такое же количество записей в вашем дереве (перемещение значений в другое место). Вы не можете уменьшить временную сложность. Разница между кучей до вставки и после вставки составляет O (logn).

trincot 08.01.2023 09:32

@trincot Если используется бинарный поиск, не уменьшится ли общее количество сравнений? Предполагая, что мы используем массив для представления кучи.

taurus05 08.01.2023 09:36

Да, но это не помогает. После сравнения вам все равно придется перемещать значения, а их O (logn).

trincot 08.01.2023 09:36

Но раньше было O(log n) сравнений. Но теперь, после выполнения бинарного поиска, выполняется O(log log n) сравнений. Это верно ? Разве нельзя сказать, что это улучшение?

taurus05 08.01.2023 09:39

Это было бы возможно с некоторыми дополнительными накладными расходами, но ваш вопрос (выделенный жирным шрифтом) гласит: «Цель состоит в том, чтобы уменьшить временную сложность метода heapify», чего не произойдет.

trincot 08.01.2023 09:40

Да, это правильно. Но я также упомянул, что This is possible only when the number of comparisons are reduced. Это неправильно?

taurus05 08.01.2023 09:41

Это действительно необходимое условие, но не достаточное.

trincot 08.01.2023 09:42
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
11
59
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Временная сложность операции вставки в кучу зависит от количества выполненных сравнений. Можно представить себе использование некоторых накладных расходов для реализации интеллектуального бинарного поиска по пути от листа к корню.

Однако временная сложность определяется не только количеством сравнений. Временная сложность определяется любой работой, которую необходимо выполнить, и в этом случае количество операций записи также равно 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𝑛).
greybeard 08.01.2023 12:13

Да, я молча предположил, что (заявленная) оптимизация всплытия также применима к просеиванию. Если это утверждение не связано с улучшением, аналогичным просеиванию, то сложность сортировки кучи не улучшается.

trincot 08.01.2023 12:15

Цель состоит в том, чтобы уменьшить временную сложность метода heapify.

Жаль, потому что это невозможно, в отличие от

Уменьшите временную сложность нескольких вставок и удалений:

Представьте, что вы не сразу вставляете в кучу n элементов,
построение вспомогательного (или даже списка).
При удалении (извлечении?) поместите один элемент из вспомогательного (теперь размером k) «в пустое место» и выполните просеивание вниз или вверх по мере необходимости, если k << n.
Если вспомогательная структура данных не намного меньше основной, объедините их.

Такие размышления приводят к продвинутым кучам вроде Фибоначчи, спаривания, Бродала…

Другие вопросы по теме