En la discusión de la estructura de datos de montón, por ejemplo en CLRS, la cola de máxima prioridad solo necesita INSERTAR, MÁXIMA, EXTRAER-MÁX y CLAVE AUMENTAR. ¿Pero por qué no tiene también DECREASE-KEY, por lo menos, su operación también invalidará la propiedad Heap? ¿Es prácticamente irrelevante?¿Por qué la cola de máxima prioridad no tiene DECREASE-KEY?
FWIW my CLR V1 habla de INSERT, MIN, EXTRACT-MIN, UNION, DECREASE-KEY, y DELETE, pero podemos convertirlo a su versión dando la vuelta a los letreros.
Creo que este conjunto está impulsado por los requisitos de los algoritmos que usan colas de prioridad, como el árbol de expansión mínima, el camino más corto de Dijstra y (sospecho) A *. Por ejemplo, si mira el comienzo del capítulo sobre árboles de expansión mínima, puede ver una nota que el algoritmo de Prim puede acelerarse si reemplaza montones binarios con montones de fibonacci.
"my CLR V1"? ¿Puedes explicar por favor? Exactamente, lo que estaba preguntando en realidad corresponde a "¿Por qué la cola de prioridad mínima no tiene INCREASE-KEY?" –
"my CLR v1" se refiere a la primera edición del libro, que no tenía a Stein como autor. Sin embargo, el segundo párrafo responde a su pregunta: los algoritmos que utilizan colas de prioridad solo necesitan poder mover entradas antes en la cola, no más tarde. – Novelocrat
Nada le impide implementar DECREASE-KEY en su pila binaria. Se puede hacer en O (log N) sin romper ninguna invariante.
Supongo que no está incluido, porque no se necesita con mucha frecuencia.
¿Cuál es su pseudo código para implementar esto? ¿Simplemente heapify en la ubicación actual? –
Suponiendo que "heapify" significa mover el nodo actual hacia abajo hasta que las invariantes del montón estén satisfechas, entonces sí. – svick
Si tiene MAX-HEAP, DECREASE-KEY será MAX-HEAPIFY en la sección 6.2 "Mantenimiento de la propiedad Heap" de CLRS, 3ª edición.
Creo que esto está relacionado con la forma en que las colas de prioridad mínima no suelen tener INCREASE-KEY, a pesar de que es una operación perfectamente bien definida. Creo que esto es algo que no surge mucho. Además, ¡no obtendrás exactamente la reputación de 1337! – templatetypedef
Podría jurar que hice esta misma pregunta antes, pero no puedo encontrarla. –
https://cs.stackexchange.com/questions/10203/increase-key-and-decrease-key-in-a-binary-min-heap – max