función cambiar_prioridad(cola, x, nueva): i ← cola.posición[x] # tabla hash: O(1) esperado vieja ← cola.prioridad[i] cola.prioridad[i] ← nueva si nueva < vieja: subir(cola, i) # más urgente: sube si no: bajar(cola, i) # menos urgente: baja
Y subir y bajar actualizan cola.posición en cada intercambio. Con la cola de la figura, cambiar_prioridad(C, 1) pasa por estos tres estados:
Paso 1 de 3. cambiar_prioridad(C, 1): la tabla dice que C está en la posición 2. No hay que recorrer el heap.Paso 2 de 3. La prioridad de C pasa de 7 a 1. Su padre, en la posición 0, es B con 3: 1 es menor, así que C sube.Paso 3 de 3. C sube a la posición 0 y B baja a la 2. El mismo intercambio actualiza las dos entradas de la tabla.
Borde grueso: lo que se compara. Relleno con asterisco: lo que acaba de cambiar.
Es la combinación de dos estructuras: un heap para el orden y una tabla hash para encontrar. Combinar estructuras para cubrir varias operaciones es habitual: lo verás en la caché LRU de la unidad 8.
En la ruta de Algoritmos, el algoritmo de Dijkstra usa exactamente esta cola para elegir el siguiente vértice más cercano.
Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.