Поддерживает ли двоичная куча операцию уменьшения ключа?

Question

В соответствии с http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants, требуется Θ (logn) (что переводится как O (logn)) для выполнения операции клавиши уменьшения. Однако, по-видимому, не существует сайта, который включает реализацию двоичной кучи с операцией уменьшения ключа.

Учитывая, таким образом, отсутствие реализаций в Интернете, возможно ли выполнить операцию уменьшения ключа в двоичной куче?

Answer 1

Я понял это:

• Чтобы выполнить клавишу понижения в O (logn), мы должны знать местоположение соответствующего элемента заранее.Хеш-карта и хорошая хеш-функция могут гарантировать O (1) амортизированное время.После каждой модификации мы должны обновлять хэш-карту, которая принимает O (logn).
• После определения местоположения нашего элемента мы перемещаем наш элемент вверх, если он имеет больший приоритет, чем его родитель (ваналогично вставке) или вниз, если он имеет более низкий приоритет, чем один из его дочерних элементов (аналогично удалению), и обновите местоположения измененных элементов в хэш-карте.