Un algoritmo es tan bueno como la estructura de datos sobre la que trabaja. En las lecciones anteriores lo hemos visto de refilón: un dict convirtió el detector de duplicados de Rutalia de cuadrático a lineal, y una tabla hizo viable la programación dinámica. En esta lección sistematizamos ese conocimiento: repasaremos brevemente las estructuras básicas y estudiaremos en profundidad cuatro estructuras que multiplican el alcance de un desarrollador: el heap (cola de prioridad), la tabla hash, el union-find y el trie. Para cada una: cómo funciona, qué cuestan sus operaciones, cuándo usarla y cómo la usa Rutalia.

1. Repaso rápido: array, lista enlazada, pila y cola
2. Heap y colas de prioridad (heapq)
3. Tablas hash: dict y set
4. Union-Find (conjuntos disjuntos)
5. Tries (árboles de prefijos)
6. Guía de elección

Estas cuatro estructuras se dan por conocidas; la tabla fija vocabulario y costes, que usaremos como referencia:

Dos avisos prácticos:

• No uses list como cola FIFO: pop(0) desplaza todos los elementos, O(n) por operación. collections.deque hace popleft() en O(1).
• La pila de llamadas de la lección 01-03 es, literalmente, una pila: LIFO de marcos de función.

Estas estructuras responden bien a "dame el último", "dame el primero" o "dame el i-ésimo". Las cuatro que siguen responden a preguntas más ricas: "dame el más urgente", "¿existe este id?", "¿están estas dos zonas conectadas?", "¿qué direcciones empiezan por...?".

Al centro de operaciones llegan pedidos continuamente, cada uno con una prioridad (hora límite de entrega). Los despachadores necesitan, una y otra vez, el pedido más urgente pendiente. Con una list: o se busca el mínimo cada vez (O(n) por extracción) o se mantiene la lista ordenada (O(n) por inserción). Con un millón de operaciones diarias, ambas opciones son cuadráticas en total.

Un heap binario de mínimos es un árbol binario completo (todos los niveles llenos salvo quizá el último, que se rellena de izquierda a derecha) que cumple la propiedad de heap: cada nodo es ≤ que sus hijos. Consecuencias:

• El mínimo está siempre en la raíz: consultarlo es O(1).
• El árbol está equilibrado por construcción: su altura es ⌊log₂ n⌋.
• Insertar: se coloca el elemento al final y se le hace "flotar" mientras sea menor que su padre → O(log n).
• Extraer el mínimo: se retira la raíz, se sube el último elemento a la raíz y se le hace "hundirse" intercambiándolo con el menor de sus hijos → O(log n).

Y el truco de implementación que lo hace tan eficiente: al ser completo, se almacena en un simple array sin punteros. El nodo i tiene hijos en 2i+1 y 2i+2, y padre en (i−1)//2.

El módulo heapq opera sobre una list normal tratándola como heap de mínimos. Para prioridades compuestas se usan tuplas (se comparan elemento a elemento):

Detalles importantes:

• heapq es siempre de mínimos. Para un heap de máximos, se insertan las claves negadas (-prioridad).
• Si dos tuplas empatan en el primer campo, se compara el segundo; incluir un contador incremental como desempate evita errores al comparar objetos no comparables: (prioridad, contador, pedido).
• Procesar n pedidos con push+pop cuesta O(n log n) en total, frente al O(n²) de las soluciones con lista.

Cuándo usarlo: siempre que se necesite repetidamente "el mejor/menor/más urgente" de un conjunto que cambia dinámicamente. Adelantamos una conexión que explotará en el módulo 3: el algoritmo de Dijkstra para caminos mínimos (lección 03-03) es, en esencia, un bucle sobre una cola de prioridad; sin heap sería impracticable a escala de ciudad.

Atención al cliente recibe: "¿dónde está mi pedido P-58201?". Con la lista de pedidos, cada consulta es una búsqueda lineal O(n). Con miles de consultas diarias sobre un millón de pedidos, inaceptable.

Una tabla hash almacena pares clave→valor en un array de m posiciones (cubetas). Una función hash convierte cada clave en un índice: indice = hash(clave) % m. Idealmente, encontrar una clave es calcular su hash e ir directo a la cubeta: O(1) sin importar n.

El problema inevitable: dos claves pueden caer en la misma cubeta (colisión). A nivel conceptual, las dos familias de soluciones:

• Encadenamiento: cada cubeta guarda una pequeña lista de los pares que caen en ella; buscar es recorrer esa lista.
• Direccionamiento abierto: si la cubeta está ocupada, se prueba en otra siguiendo una secuencia de sondeo (es lo que hace CPython para dict).

Mientras el factor de carga (n/m) se mantenga bajo y la función hash reparta bien, las cadenas/sondeos son cortos y las operaciones cuestan O(1) en media. Cuando la tabla se llena demasiado, se redimensiona (rehash) — un coste puntual O(n) que, como el append de la lección 01-02, queda en O(1) amortizado. El peor caso teórico (todas las claves colisionando) es O(n), pero con las funciones hash de Python es irrelevante en la práctica habitual.

dict (clave→valor) y set (solo claves) son tablas hash nativas:

Requisito: las claves deben ser hashables (inmutables): números, cadenas, tuplas de inmutables. Las listas y dicts no pueden ser claves — de ahí que en la lección 01-03 memoizáramos con tuplas (f, c).

Cuándo usarla: membresía, indexación por clave, deduplicación, conteo (collections.Counter). Es la estructura que ya salvó al detector de duplicados en 01-02. Cuándo no: si necesitas orden por clave o rangos ("pedidos entre las 10:00 y las 11:00"), la tabla hash no ayuda; ahí entran los datos ordenados y la búsqueda binaria (lección 04-01).

La ciudad está dividida en zonas de reparto. Algunas calles entre zonas se cortan (obras, mercados); el sistema recibe eventos "la zona A y la zona B han quedado conectadas por un paso abierto" y consultas "¿puedo llegar de la zona X a la zona Y solo por pasos abiertos?". Se necesita agrupar elementos en componentes que se van fusionando, y preguntar rápidamente si dos elementos están en el mismo grupo.

Union-Find (o disjoint set union, DSU) mantiene una colección de conjuntos disjuntos con dos operaciones:

• find(x): devuelve el representante del conjunto de x (dos elementos están en el mismo conjunto si y solo si tienen el mismo representante).
• union(x, y): fusiona los conjuntos de x e y.

Implementación: cada elemento apunta a un "padre"; el representante es la raíz de ese árbol de punteros. Ingenuamente los árboles pueden degenerar en cadenas (find O(n)); dos optimizaciones clásicas lo evitan:

• Unión por rango: al fusionar, la raíz del árbol más bajo se cuelga de la del más alto, manteniendo los árboles poco profundos.
• Compresión de caminos: cada find reengancha directamente a la raíz todos los nodos que visita, aplanando el árbol para el futuro.

Con ambas, el coste amortizado por operación es O(α(n)), donde α es la inversa de la función de Ackermann: crece tan despacio que α(n) ≤ 4 para cualquier n físicamente posible. En la práctica: constante.

Línea a línea, lo esencial:

• find es recursivo: sube hasta la raíz y, al volver, reescribe cada padre[x] apuntando directamente a ella. La siguiente consulta sobre cualquiera de esos nodos será un salto directo.
• union devuelve False si los elementos ya estaban conectados — un detalle utilísimo para detectar ciclos.

Limitación: union-find solo fusiona; no soporta "cerrar un paso" (des-unir) eficientemente. Si las conexiones también se destruyen, hacen falta otras técnicas.

Cuándo usarlo: conectividad incremental, agrupamiento, detección de ciclos. Otra conexión hacia delante: el algoritmo de Kruskal para árboles de expansión mínima (lección 03-04) consiste en recorrer aristas ordenadas preguntando a un union-find si cada arista conecta componentes distintas.

La app de los repartidores autocompleta direcciones: el usuario teclea "cal" y deben aparecer "Calle Mayor", "Calle Malva", "Calzada Real"… Buscar con startswith sobre la lista completa es O(n·L) por pulsación (n direcciones de longitud media L). Se necesita una estructura que organice las cadenas por sus prefijos.

Un trie es un árbol donde cada arista lleva un carácter; cada nodo representa el prefijo formado por el camino desde la raíz, y los nodos terminales marcan palabras completas. Todas las palabras con un prefijo común comparten el camino de ese prefijo.

Costes, con L = longitud de la cadena consultada (¡no dependen del número n de palabras!):

Cómo funciona el código:

• Cada nodo es simplemente un dict de hijos: aprovechamos la tabla hash de la sección 3 como bloque de construcción (composición de estructuras — patrón habitual).
• insertar baja creando nodos según hace falta: exactamente L pasos.
• con_prefijo tiene dos fases: bajar por el prefijo (O(L)) y recorrer el subárbol acumulando palabras. Para autocompletar, en la práctica se limita el número de resultados devueltos.

Cuándo usarlo: autocompletado, correctores, rutas jerárquicas, búsqueda por prefijo en general. Cuándo no: si solo se necesita búsqueda exacta, un set es más simple y compacto; el trie paga su memoria extra solo cuando los prefijos importan.

La pregunta que resuelve cada estructura, en una tabla de decisión:

En el sistema de Rutalia conviven todas: un dict indexa los pedidos por id, un heap ordena el despacho por urgencia, un union-find responde sobre zonas conectadas y un trie autocompleta el callejero. Elegir estructura es traducir la pregunta más frecuente del sistema a la fila correcta de esta tabla.

• Usar list como cola FIFO o como conjunto. pop(0) es O(n) y x in lista es O(n). Son probablemente los dos errores de rendimiento más comunes en Python: deque y set los resuelven de raíz.
• Buscar dentro de un heap. El heap solo garantiza dónde está el mínimo; localizar o actualizar un elemento arbitrario es O(n). El patrón estándar para "cambiar la prioridad" es insertar la entrada nueva y descartar la vieja al extraerla (marcándola como obsoleta).
• Meter objetos no comparables en heapq. Si dos tuplas empatan en la prioridad, Python compara el siguiente campo; si es un dict, excepción. Solución: tupla (prioridad, contador, objeto) con un contador incremental.
• Usar claves mutables en dict/set. Las listas no son hashables (error inmediato); y aunque un objeto propio sea hashable, mutarlo tras insertarlo corrompe su localización en la tabla. Claves inmutables, siempre.
• Confiar en el orden de un dict como orden de clave. Los dict de Python conservan el orden de inserción, no el orden de las claves. Para rangos u ordenación, hay que ordenar aparte.
• Implementar union-find sin las dos optimizaciones. Sin compresión ni rango, los árboles degeneran y cada find puede ser O(n); con secuencias grandes de uniones la diferencia es de horas a segundos. Son cinco líneas: inclúyelas siempre.
• Elegir trie para búsqueda exacta. Si nunca preguntas por prefijos, el trie solo aporta consumo de memoria y complejidad. La estructura más simple que responda tu pregunta dominante es la correcta.
• Consejo: antes de escribir código, formula en una frase la operación más frecuente de tu sistema ("necesito X millones de veces al día...") y busca su fila en la tabla de la sección 6. Ese minuto de reflexión evita la mayoría de reescrituras.

Implementa despachar(pedidos, k) que reciba una lista de tuplas (hora_limite, id) y devuelva los k pedidos más urgentes en orden, usando heapq. Indica la complejidad de tu solución y compárala con ordenar la lista completa. ¿Cuál conviene si n = 1 000 000 y k = 10?

Rutalia tiene n zonas (0..n−1) y una lista de pasos abiertos pasos = [(a, b), ...]. Escribe componentes(n, pasos) que devuelva cuántos grupos de zonas mutuamente alcanzables hay, usando la clase UnionFind de la lección. Ejemplo: componentes(6, [(0,1), (1,2), (4,5)]) → 3 (grupos {0,1,2}, {3}, {4,5}).

Amplía la clase Trie con un método contar_prefijo(prefijo) que devuelva cuántas direcciones empiezan por el prefijo, en O(L) —sin recorrer el subárbol—. Pista: almacena en cada nodo un contador que se incremente al insertar.

Solución 1

Complejidad: O(n + k·log n). Ordenar la lista completa es O(n log n). Con n = 10⁶ y k = 10: ~10⁶ + 10·20 operaciones frente a ~2·10⁷; el heap gana con claridad porque no paga por ordenar lo que no se despacha. (Aún más directo: heapq.nsmallest(k, pedidos) hace esencialmente esto.) Si k ≈ n, ambas opciones convergen a O(n log n) y ordenar es más simple.

Solución 2

Coste: O(n + m·α(n)) para m pasos — prácticamente lineal. El truco de contar con el valor de retorno de union evita un recorrido final buscando raíces distintas. Error común: contar cada llamada a union como fusión sin comprobar si ya estaban conectadas.

Solución 3

Cada nodo lleva cuántas palabras atraviesan ese prefijo; contar_prefijo solo baja L niveles → O(L), independiente del número de direcciones. (Con esta variante, las claves "#" y FIN conviven con los caracteres hijos; el recorrido de con_prefijo debe saltarse ambas. Si se insertan palabras repetidas, el contador las cuenta todas — decide si eso es lo que quieres.)

Cerramos el primer módulo con la caja de herramientas completa. Las estructuras básicas (array, lista enlazada, pila, cola) responden preguntas posicionales; las avanzadas responden preguntas de mayor valor: el heap entrega el elemento más prioritario en O(log n) y es el motor de las colas de prioridad de heapq; la tabla hash (dict/set) da membresía e indexación en O(1) medio a cambio de renunciar al orden; el union-find con compresión de caminos y unión por rango mantiene grupos que se fusionan en tiempo prácticamente constante; y el trie organiza cadenas por prefijos, haciendo el autocompletado independiente del tamaño del callejero. En Rutalia, cada una resuelve una pregunta concreta del negocio: priorizar pedidos urgentes, localizar un pedido al instante, saber si dos zonas siguen conectadas y sugerir direcciones mientras se teclea. Y hemos dejado dos semillas plantadas: el heap es la pieza que hará eficiente a Dijkstra (lección 03-03) y el union-find, a Kruskal (lección 03-04).

Con esto termina la introducción: sabemos expresar costes (01-01), calcularlos (01-02), diseñar con recursión y programación dinámica (01-03) y apoyarnos en las estructuras adecuadas (01-04). En el módulo 2, Algoritmos de Optimización, pasamos de analizar a decidir: Rutalia ya no preguntará "¿cuánto cuesta esta operación?" sino "¿cuál es la mejor asignación de recursos posible?" — empezando por la programación lineal (02-01) y siguiendo con optimización combinatoria, backtracking y branch and bound, algoritmos genéticos y colonias de hormigas.