¿Admite un montón binario la operación de disminución de tecla?

Question

Según http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants, se necesita Θ (logn) (que se traduce en O (logn)) para realizar la operación de disminución de la tecla. Sin embargo, parece que no hay ningún sitio que incluya una implementación de pila binaria con una operación de tecla de disminución.

Dada la falta de implementaciones en la web, ¿es posible realizar la operación de disminución de la clave en un montón binario?

Answer 1

me cuenta de esto:

• Con el fin de realizar una tecla disminución en O (log n), tenemos que conocer la ubicación del elemento correspondiente con antelación. Un hash map y una buena función hash pueden garantizar O (1) tiempo amortizado. Después de cada modificación, tenemos que actualizar el mapa hash, que toma O (logn).
• Después de determinar la ubicación de nuestro elemento, movemos nuestro elemento hacia arriba en caso de que tenga una prioridad mayor que su elemento principal (de manera similar a la inserción) o hacia abajo si tiene una prioridad menor que uno de sus elementos secundarios (en similar a la eliminación) y actualizar las ubicaciones de los elementos modificados en el mapa hash.