Algoritmos y Estructuras de Datos (VJ1215)

Para cambiar la prioridad de un dato en un montículo binario, conociendo su posición, podemos utilizar las operaciones hundir (percolate-down) o flotar (percolate-up), dependiendo de si la nueva prioridad es mayor o menor que la anterior:

• En un montículo de mínimos (min-heap) utilizaríamos la operación flotar si disminuye la prioridad y hundir si aumenta.

• En un montículo de máximos (max-heap) utilizaríamos la operación flotar si aumenta la prioridad y hundir si disminuye.

Eso tiene coste temporal O(log n) en el peor caso y O(1) en el mejor caso, siendo n la cantidad de elementos en el montículo.

El coste no sería ese si hubiera que buscar primero el dato: eso costaría O(n) porque deberíamos recorrer el vector en el que el montículo está representado implícitamente, para comprobar si el dato está en cualquiera de sus posiciones.