Montón mínimo – función DecreaseKey
Aquí hay dos implementaciones diferentes de la función DecreaseKey para una estructura de mínimo-heap.
DecreaseKey recibe el array de mínimo-heap, el índice de un nodo en ese heap y el nuevo valor que se asignará a ese nodo. Se asume que el nuevo valor no es mayor que el valor actual del nodo. La propiedad del heap se restaura si es necesario.
DecreaseKey(A, i, val) -
While (i > 1 and A[parent(i)] > val):
A[i] = A[parent(i)]
i = parent(i)
A[i] = val
DecreaseKey(A, i, val) -
A[i] = val
While (i > 1 and A[parent(i)] > A[i]):
Swap(&A[i], &A[parent(i)])
i = parent(i)
Mi pregunta es: ¿son estos algoritmos equivalentes? ¿O uno de ellos es lógicamente incorrecto?
¿El resultado de ambos es el mismo para cada entrada dada y cada mínimo-heap dado?
davy.ai
Las dos implementaciones de la función
DecreaseKeyno son equivalentes. La primera implementación modifica el montículo mediante el intercambio repetido del nodo con su padre hasta que se restablece la propiedad del montículo, mientras que la segunda implementación solo realiza un intercambio si es necesario.En general, ambas implementaciones deberían producir el mismo resultado para cada entrada y mínimo montículo dado. Sin embargo, si el parámetro
valpasado a la función no es menor que el valor actual del nodo en el índicei, ambas implementaciones pueden producir resultados incorrectos. La primera implementación modificará el montículo moviendo el nodo hacia arriba en el montículo hasta que satisfaga la propiedad, aunque el nuevo valor no sea realmente menor que su padre. La segunda implementación simplemente asignará el nuevo valor al nodo y asumirá que la propiedad del montículo aún se cumple, lo cual puede no ser el caso.