Un min-heap con mejor que O (logn) tecla de aumento?

Question

Estoy usando una cola de prioridad que inicialmente basa la prioridad de sus elementos en una heurística. A medida que los elementos se eliminan, la heurística se actualiza y los elementos que se encuentran actualmente en la cola pueden tener sus claves aumentadas.

Sé que hay montones (montones de Fibonacci específicamente) que han amortizado O (1) disminuyen las operaciones de las teclas, pero ¿hay estructuras de montón que tengan límites similares en las operaciones de aumento de la tecla?

Para mi aplicación esto está lejos de ser un problema de rendimiento (un montón binario funciona bien) es realmente solo curiosidad académica.

Editar: para aclarar, estoy buscando una estructura de datos que tenga un tiempo más rápido que O (logn) para el aumentar la operación de la clave, no disminuir la clave. Mi aplicación nunca disminuye la clave ya que la heurística sobreestima la prioridad.

Answer 1

Los montones binarios son demasiado flexibles para vencer la complejidad logarítmica. Los montones binomiales solo permiten una operación de unión más eficiente.

Otros montones con un buen rendimiento clave disminución-son pairing heaps y 2-3 heaps

Answer 2

montones binomiales toman O (log n) tiempo para las operaciones clave disminución! ¿No es esto más lento que los montones de fibonacci?

Answer 3

En realidad, con montones de Fibonacci, el aumento de la operación de la tecla es igual que la tecla de disminución. En mi humilde opinión, es solo una tradición nombrar la operación "tecla de disminución", porque se usa en algunos algoritmos. Pero la implementación del montón de Fibonacci permite ambos.