Как добиться времени O(log(n)) для уменьшения ключа в биномиальной куче
Почти в каждом месте, которое я читаю, утверждается, что уменьшение ключа в биноминальной куче занимает время O(log(n)). Хотя это имеет смысл, поскольку сама операция требует этого времени, они не учитывают поиск ключа, который должен быть уменьшен, что занимает время O(n), что приводит к общему времени O(nlog(n)), которое это большая разница.
Я читал, что вы можете хранить указатели на каждый ключ в хеш-таблице, и это обновляет ключи таким образом, но это увеличивает сложность пространства.
Итак, мой вопрос заключается в следующем: нормально ли хранить указатели для каждого ключа в хэш-таблице и является ли дополнительное пространство незначительным? Или есть какой-то лучший способ достижения времени O(log(n)) без использования хеш-таблицы.