Мин-куча с ключом увеличения лучше чем O (logn)?

Question

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

Я знаю, что есть кучи (особенно кучи Фибоначчи), которые амортизируют O (1), уменьшают ключевые операции, но есть ли структуры кучи, которые имеют аналогичные границы для операций увеличения ключа?

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

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

Answer 1

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

Другими кучами с хорошей производительностью ключа уменьшения являются пары кучи и 2-3 кучи

Answer 2

На самом деле, с кучами Фибоначчи, операция клавиши увеличения аналогична клавише уменьшения. ИМХО, это только традиция называть операцию «ключ уменьшения», потому что она используется в некоторых алгоритмах. Но реализация кучи Фибоначчи допускает и то и другое.

Answer 3

Биноминальные кучи занимают o (log n) времени для уменьшения ключевых операций! Разве это не медленнее, чем кучи Фибоначчи?