data-structures - publico - reduccion de mamas por problemas de columna

¿Un montón binario admite la operación de disminución de la tecla?

Question

De acuerdo con http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variantes , 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 di cuenta de esto:

• Para realizar una tecla de disminución en O (logn), debemos conocer la ubicación del elemento correspondiente de antemano. 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 padre (de manera similar a la inserción) o hacia abajo si tiene una prioridad menor que uno de sus hijos (de manera similar a eliminación) y actualizar las ubicaciones de los elementos modificados en el mapa hash.