Saltar al contenido
wandres.dev
Iniciar sesión

Modelo por capas

La interfaz de cola de prioridad

Una cola de prioridad es la interfaz:

  • insertar(x, prioridad);
  • mínimo(): ver el de mayor urgencia (menor valor);
  • extraer_mínimo();
  • a veces, cambiar_prioridad(x, nueva).

El heap implementa las tres primeras en O(log n), O(1) y O(log n). La cuarta tiene un problema: encontrar x en el heap es O(n), porque el heap no ordena entre ramas.

Este dibujo muestra un heap de cinco elementos y su índice de posiciones, la primera solución:

Un heap con su índice de posicionesUn heap de cinco elementos como array: B con prioridad 3 en la posición 0, A con 5 en la 1, C con 7 en la 2, D con 9 en la 3 y E con 8 en la 4. Debajo, una tabla hash que guarda para cada elemento su posición: A va a la 1, B a la 0, C a la 2, D a la 3 y E a la 4. Una flecha une cada entrada con su celda.heap (el orden)B 30A 51C 72D 93E 84índice de posiciones (tabla hash): elemento → posiciónA → 1B → 0C → 2D → 3E → 4
El heap guarda el orden; la tabla guarda dónde está cada elemento. La posición de cada celda aparece sobre ella; cada flecha va de una entrada de la tabla a la celda donde está ese elemento.

Dos soluciones:

  • Índice de posiciones: una tabla hash que guarda, para cada elemento, su posición actual en el array. Cada intercambio la actualiza. Así, cambiar la prioridad es O(log n): buscar la posición en la tabla y subir o bajar.
  • Borrado perezoso: no se cambia nada; se inserta el elemento otra vez con la prioridad nueva. Al extraer, si sale una copia vieja, se descarta.
El heap [(A, 1), (B, 4), (C, 2)] tiene el índice {A: 0, B: 1, C: 2}. Insertas (D, 0) en la posición 3, hijo de B, y sube hasta la raíz. ¿Cómo queda el índice al terminar?