El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Estructures de Dades Avançades

Següent ►
►

Un algorisme és tan bo com l'estructura de dades sobre la qual treballa. A les lliçons anteriors ho hem vist de passada: un dict va convertir el detector de duplicats de Rutalia de quadràtic a lineal, i una taula va fer viable la programació dinàmica. En aquesta lliçó sistematitzem aquest coneixement: repassarem breument les estructures bàsiques i estudiarem en profunditat quatre estructures que multipliquen l'abast d'un desenvolupador: el heap (cua de prioritat), la taula de hash, el union-find i el trie. Per a cadascuna: com funciona, què costen les seves operacions, quan fer-la servir i com la fa servir Rutalia.

Contingut

  1. Repàs ràpid: array, llista enllaçada, pila i cua
  2. Heap i cues de prioritat (heapq)
  3. Taules de hash: dict i set
  4. Union-Find (conjunts disjunts)
  5. Tries (arbres de prefixos)
  6. Guia d'elecció

  1. Repàs ràpid: array, llista enllaçada, pila i cua

Aquestes quatre estructures es donen per conegudes; la taula fixa vocabulari i costos, que farem servir com a referència:

Estructura En Python Accés per índex Inserció/esborrat al final Inserció/esborrat al principi Cerca per valor
Array dinàmic list O(1) O(1) amortitzat (lliçó 01-02) O(n) O(n)
Llista enllaçada (no nativa; deque és el més semblant) O(n) O(1) amb punter al final O(1) O(n)
Pila (LIFO) list amb append/pop — O(1) — —
Cua (FIFO) collections.deque amb append/popleft — O(1) O(1) —

Dos avisos pràctics:

  • No facis servir list com a cua FIFO: pop(0) desplaça tots els elements, O(n) per operació. collections.deque fa popleft() en O(1).
  • La pila de crides de la lliçó 01-03 és, literalment, una pila: LIFO de marcs de funció.

Aquestes estructures responen bé a "dona'm l'últim", "dona'm el primer" o "dona'm l'i-èsim". Les quatre que segueixen responen preguntes més riques: "dona'm el més urgent", "existeix aquest id?", "aquestes dues zones estan connectades?", "quines adreces comencen per...?".

  1. Heap i cues de prioritat (heapq)

El problema de Rutalia

Al centre d'operacions arriben comandes contínuament, cadascuna amb una prioritat (hora límit de lliurament). Els despatxadors necessiten, una vegada i una altra, la comanda més urgent pendent. Amb una list: o es cerca el mínim cada vegada (O(n) per extracció) o es manté la llista ordenada (O(n) per inserció). Amb un milió d'operacions diàries, totes dues opcions són quadràtiques en total.

L'estructura

Un heap binari de mínims és un arbre binari complet (tots els nivells plens llevat potser de l'últim, que s'omple d'esquerra a dreta) que compleix la propietat de heap: cada node és ≤ que els seus fills. Conseqüències:

  • El mínim és sempre a l'arrel: consultar-lo és O(1).
  • L'arbre està equilibrat per construcció: la seva altura és ⌊log₂ n⌋.
  • Inserir: es col·loca l'element al final i se'l fa "surar" mentre sigui menor que el seu pare → O(log n).
  • Extreure el mínim: es retira l'arrel, es puja l'últim element a l'arrel i se'l fa "enfonsar" intercanviant-lo amb el menor dels seus fills → O(log n).

I el truc d'implementació que el fa tan eficient: com que és complet, s'emmagatzema en un simple array sense punters. El node i té els fills a 2i+1 i 2i+2, i el pare a (i−1)//2.

flowchart TD
    A["10:15<br/>(arrel = mínim)"] --> B["10:40"]
    A --> C["11:00"]
    B --> D["12:30"]
    B --> E["10:55"]
    C --> F["11:20"]
Operació Cost Nota
veure el mínim O(1) l'arrel
inserir O(log n) surar
extreure el mínim O(log n) enfonsar-se
construir des de n elements O(n) heapify, millor que n insercions
cercar un element arbitrari O(n) el heap NO serveix per cercar!

En Python: heapq

El mòdul heapq opera sobre una list normal tractant-la com un heap de mínims. Per a prioritats compostes es fan servir tuples (es comparen element a element):

import heapq

# Cua de prioritat de comandes: (hora_limit, id_comanda)
pendents = []
heapq.heappush(pendents, ("12:30", "P-0001"))
heapq.heappush(pendents, ("10:15", "P-0002"))
heapq.heappush(pendents, ("11:00", "P-0003"))

print(pendents[0])                    # ('10:15', 'P-0002') — veure sense extreure, O(1)

seguent = heapq.heappop(pendents)     # extreu la més urgent, O(log n)
print(seguent)                        # ('10:15', 'P-0002')

# Construir de cop a partir de la llista del dia: O(n)
del_dia = [("13:00", "P-0004"), ("09:45", "P-0005"), ("10:30", "P-0006")]
heapq.heapify(del_dia)                # ara del_dia és un heap vàlid

Detalls importants:

  • heapq és sempre de mínims. Per a un heap de màxims, s'insereixen les claus negades (-prioritat).
  • Si dues tuples empaten en el primer camp, es compara el segon; incloure un comptador incremental com a desempat evita errors en comparar objectes no comparables: (prioritat, comptador, comanda).
  • Processar n comandes amb push+pop costa O(n log n) en total, davant de l'O(n²) de les solucions amb llista.

Quan fer-lo servir: sempre que es necessiti repetidament "el millor/menor/més urgent" d'un conjunt que canvia dinàmicament. Avancem una connexió que explotarà al mòdul 3: l'algorisme de Dijkstra per a camins mínims (lliçó 03-03) és, en essència, un bucle sobre una cua de prioritat; sense heap seria impracticable a escala de ciutat.

  1. Taules de hash: dict i set

El problema de Rutalia

Atenció al client rep: "on és la meva comanda P-58201?". Amb la llista de comandes, cada consulta és una cerca lineal O(n). Amb milers de consultes diàries sobre un milió de comandes, inacceptable.

L'estructura

Una taula de hash emmagatzema parells clau→valor en un array de m posicions (cubetes). Una funció de hash converteix cada clau en un índex: index = hash(clau) % m. Idealment, trobar una clau és calcular-ne el hash i anar directe a la cubeta: O(1) sense que importi n.

El problema inevitable: dues claus poden caure a la mateixa cubeta (col·lisió). A nivell conceptual, les dues famílies de solucions:

  • Encadenament: cada cubeta guarda una petita llista dels parells que hi cauen; cercar és recórrer aquesta llista.
  • Adreçament obert: si la cubeta està ocupada, es prova en una altra seguint una seqüència de sondeig (és el que fa CPython per al dict).

Mentre el factor de càrrega (n/m) es mantingui baix i la funció de hash reparteixi bé, les cadenes/sondeigs són curts i les operacions costen O(1) de mitjana. Quan la taula s'omple massa, es redimensiona (rehash) — un cost puntual O(n) que, com l'append de la lliçó 01-02, queda en O(1) amortitzat. El pitjor cas teòric (totes les claus col·lidint) és O(n), però amb les funcions de hash de Python és irrellevant en la pràctica habitual.

Operació dict / set list
x in coleccio O(1) mitjana O(n)
inserir O(1) mitjana/amortitzada O(1) al final
esborrar per clau O(1) mitjana O(n)
recórrer-ho tot O(n) O(n)
mínim/màxim O(n) O(n)
recorregut en ordre de clau no directe (cal ordenar) no directe

En Python

dict (clau→valor) i set (només claus) són taules de hash natives:

# Índex de comandes per id: construcció O(n), consulta O(1)
comandes = [
    {"id": "P-58200", "estat": "en repartiment", "adreca": "Carrer Major 4"},
    {"id": "P-58201", "estat": "al magatzem", "adreca": "Av. del Parc 21"},
]
per_id = {c["id"]: c for c in comandes}

print(per_id["P-58201"]["estat"])        # 'al magatzem' — O(1) mitjana

# set: aquest codi postal és dins la zona de cobertura?
zones_cobertes = {"08001", "08002", "08015", "08025"}
print("08015" in zones_cobertes)         # True — O(1) mitjana

Requisit: les claus han de ser hashables (immutables): nombres, cadenes, tuples d'immutables. Les llistes i els dicts no poden ser claus — per això a la lliçó 01-03 memoitzàvem amb tuples (f, c).

Quan fer-la servir: pertinença, indexació per clau, deduplicació, recompte (collections.Counter). És l'estructura que ja va salvar el detector de duplicats a 01-02. Quan no: si necessites ordre per clau o rangs ("comandes entre les 10:00 i les 11:00"), la taula de hash no ajuda; aquí entren les dades ordenades i la cerca binària (lliçó 04-01).

  1. Union-Find (conjunts disjunts)

El problema de Rutalia

La ciutat està dividida en zones de repartiment. Alguns carrers entre zones es tallen (obres, mercats); el sistema rep esdeveniments "la zona A i la zona B han quedat connectades per un pas obert" i consultes "puc arribar de la zona X a la zona Y només per passos oberts?". Cal agrupar elements en components que es van fusionant, i preguntar ràpidament si dos elements són al mateix grup.

L'estructura

Union-Find (o disjoint set union, DSU) manté una col·lecció de conjunts disjunts amb dues operacions:

  • find(x): retorna el representant del conjunt de x (dos elements són al mateix conjunt si i només si tenen el mateix representant).
  • union(x, y): fusiona els conjunts de x i y.

Implementació: cada element apunta a un "pare"; el representant és l'arrel d'aquest arbre de punters. Ingènuament els arbres poden degenerar en cadenes (find O(n)); dues optimitzacions clàssiques ho eviten:

  • Unió per rang: en fusionar, l'arrel de l'arbre més baix es penja de la del més alt, mantenint els arbres poc profunds.
  • Compressió de camins: cada find reenganxa directament a l'arrel tots els nodes que visita, aplanant l'arbre per al futur.

Amb totes dues, el cost amortitzat per operació és O(α(n)), on α és la inversa de la funció d'Ackermann: creix tan a poc a poc que α(n) ≤ 4 per a qualsevol n físicament possible. A la pràctica: constant.

class UnionFind:
    """Conjunts disjunts amb compressió de camins i unió per rang."""

    def __init__(self, n):
        self.pare = list(range(n))    # cada element comença sent la seva pròpia arrel
        self.rang = [0] * n           # fita superior de l'altura de cada arbre

    def find(self, x):
        if self.pare[x] != x:
            self.pare[x] = self.find(self.pare[x])   # compressió de camins
        return self.pare[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False              # ja eren al mateix conjunt
        if self.rang[rx] < self.rang[ry]:
            rx, ry = ry, rx           # rx passa a ser l'arrel de l'arbre més alt
        self.pare[ry] = rx            # el baix es penja de l'alt
        if self.rang[rx] == self.rang[ry]:
            self.rang[rx] += 1        # l'altura només creix si empataven
        return True


# Zones 0..5 de Rutalia; s'obren passos entre zones
zones = UnionFind(6)
zones.union(0, 1)      # pas obert entre la zona 0 i la 1
zones.union(1, 2)      # entre la 1 i la 2
zones.union(4, 5)      # entre la 4 i la 5

print(zones.find(0) == zones.find(2))   # True: 0 i 2 connectades (via 1)
print(zones.find(0) == zones.find(4))   # False: components diferents

Línia a línia, l'essencial:

  • find és recursiu: puja fins a l'arrel i, en tornar, reescriu cada pare[x] apuntant-hi directament. La consulta següent sobre qualsevol d'aquests nodes serà un salt directe.
  • union retorna False si els elements ja estaven connectats — un detall utilíssim per detectar cicles.
Operació Ingenu Amb rang + compressió
find O(n) pitjor cas O(α(n)) ≈ O(1) amortitzat
union O(n) pitjor cas O(α(n)) ≈ O(1) amortitzat
espai O(n) O(n)

Limitació: el union-find només fusiona; no suporta "tancar un pas" (desunir) de manera eficient. Si les connexions també es destrueixen, calen altres tècniques.

Quan fer-lo servir: connectivitat incremental, agrupament, detecció de cicles. Una altra connexió cap endavant: l'algorisme de Kruskal per a arbres d'expansió mínims (lliçó 03-04) consisteix a recórrer arestes ordenades preguntant a un union-find si cada aresta connecta components diferents.

  1. Tries (arbres de prefixos)

El problema de Rutalia

L'app dels repartidors autocompleta adreces: l'usuari tecleja "car" i han d'aparèixer "Carrer Major", "Carrer Malva", "Carretera Reial"… Cercar amb startswith sobre la llista completa és O(n·L) per pulsació (n adreces de longitud mitjana L). Cal una estructura que organitzi les cadenes pels seus prefixos.

L'estructura

Un trie és un arbre on cada aresta porta un caràcter; cada node representa el prefix format pel camí des de l'arrel, i els nodes terminals marquen paraules completes. Totes les paraules amb un prefix comú comparteixen el camí d'aquest prefix.

flowchart TD
    R(("arrel")) -->|c| C(("c"))
    C -->|a| CA(("ca"))
    CA -->|r| CAR(("car"))
    CAR -->|r| CARR(("carr"))
    CARR -->|e| CARRE(("carre"))
    CARRE -->|r| CARRER(("carrer ✓"))
    CARRE -->|t| CARRET(("carret..."))
    R -->|p| P(("p"))
    P -->|l| PL(("pl..."))

Costos, amb L = longitud de la cadena consultada (no depenen del nombre n de paraules!):

Operació Cost Comparació amb alternatives
inserir una paraula O(L) —
cercar una paraula exacta O(L) hash: O(L) també (cal hashejar la cadena)
existeix algun resultat amb aquest prefix? O(L) hash: impossible sense recórrer-ho tot; llista ordenada: O(L·log n)
llistar els k resultats d'un prefix O(L + mida del subarbre) llista: O(n·L)
espai O(suma de longituds), amb compartició de prefixos constant més gran que un set (molts nodes/punters) 
class Trie:
    """Trie per autocompletar adreces."""

    def __init__(self):
        self.arrel = {}         # cada node és un dict: caràcter -> node fill
        self.FI = "$"           # marca de paraula completa

    def inserir(self, paraula):
        node = self.arrel
        for ch in paraula:
            node = node.setdefault(ch, {})   # crea el fill si no existeix
        node[self.FI] = True                 # marca el final de la paraula

    def amb_prefix(self, prefix):
        """Retorna totes les paraules que comencen per `prefix`."""
        node = self.arrel
        for ch in prefix:                    # 1) baixar fins al node del prefix
            if ch not in node:
                return []                    # cap resultat
            node = node[ch]
        resultats = []                       # 2) recórrer el subarbre (DFS)
        pila = [(node, prefix)]
        while pila:
            actual, text = pila.pop()
            for ch, fill in actual.items():
                if ch == self.FI:
                    resultats.append(text)
                else:
                    pila.append((fill, text + ch))
        return resultats


nomenclator = Trie()
for adreca in ["carrer major", "carrer malva", "carretera reial", "plaça nord"]:
    nomenclator.inserir(adreca)

print(nomenclator.amb_prefix("car"))
# ['carretera reial', 'carrer malva', 'carrer major'] (l'ordre pot variar)
print(nomenclator.amb_prefix("av"))   # []

Com funciona el codi:

  • Cada node és simplement un dict de fills: aprofitem la taula de hash de la secció 3 com a bloc de construcció (composició d'estructures — patró habitual).
  • inserir baixa creant nodes a mesura que calen: exactament L passos.
  • amb_prefix té dues fases: baixar pel prefix (O(L)) i recórrer el subarbre acumulant paraules. Per a l'autocompletat, a la pràctica es limita el nombre de resultats retornats.

Quan fer-lo servir: autocompletat, correctors, rutes jeràrquiques, cerca per prefix en general. Quan no: si només cal la cerca exacta, un set és més simple i compacte; el trie paga la seva memòria extra només quan els prefixos importen.

  1. Guia d'elecció

La pregunta que resol cada estructura, en una taula de decisió:

Pregunta dominant al teu codi Estructura Cost clau
"l'i-èsim element?" list O(1)
"l'últim que ha entrat?" (LIFO) pila (list) O(1)
"el primer que ha entrat?" (FIFO) deque O(1)
"el més prioritari ara mateix?" heap (heapq) O(log n)
"existeix aquesta clau? / dona'm el seu valor" dict / set O(1) mitjana
"aquests dos són al mateix grup?" (grups que es fusionen) union-find ≈ O(1) amortitzat
"quines cadenes comencen per...?" trie O(L + resultats)

Al sistema de Rutalia hi conviuen totes: un dict indexa les comandes per id, un heap ordena el despatx per urgència, un union-find respon sobre zones connectades i un trie autocompleta el nomenclàtor. Triar estructura és traduir la pregunta més freqüent del sistema a la fila correcta d'aquesta taula.

Errors Comuns i Consells

  • Fer servir list com a cua FIFO o com a conjunt. pop(0) és O(n) i x in llista és O(n). Són probablement els dos errors de rendiment més comuns en Python: deque i set els resolen d'arrel.
  • Cercar dins d'un heap. El heap només garanteix on és el mínim; localitzar o actualitzar un element arbitrari és O(n). El patró estàndard per "canviar la prioritat" és inserir l'entrada nova i descartar la vella en extreure-la (marcant-la com a obsoleta).
  • Ficar objectes no comparables a heapq. Si dues tuples empaten en la prioritat, Python compara el camp següent; si és un dict, excepció. Solució: tupla (prioritat, comptador, objecte) amb un comptador incremental.
  • Fer servir claus mutables a dict/set. Les llistes no són hashables (error immediat); i encara que un objecte propi sigui hashable, mutar-lo després d'inserir-lo corromp la seva localització a la taula. Claus immutables, sempre.
  • Confiar en l'ordre d'un dict com a ordre de clau. Els dict de Python conserven l'ordre d'inserció, no l'ordre de les claus. Per a rangs o ordenació, cal ordenar a part.
  • Implementar union-find sense les dues optimitzacions. Sense compressió ni rang, els arbres degeneren i cada find pot ser O(n); amb seqüències grans d'unions la diferència és d'hores a segons. Són cinc línies: inclou-les sempre.
  • Triar el trie per a cerca exacta. Si mai no preguntes per prefixos, el trie només aporta consum de memòria i complexitat. L'estructura més simple que respongui la teva pregunta dominant és la correcta.
  • Consell: abans d'escriure codi, formula en una frase l'operació més freqüent del teu sistema ("necessito X milions de vegades al dia...") i cerca la seva fila a la taula de la secció 6. Aquest minut de reflexió estalvia la majoria de reescriptures.

Exercicis

Exercici 1: Despatx urgent amb heap

Implementa despatxar(comandes, k) que rebi una llista de tuples (hora_limit, id) i retorni les k comandes més urgents en ordre, fent servir heapq. Indica la complexitat de la teva solució i compara-la amb ordenar la llista completa. Quina convé si n = 1 000 000 i k = 10?

Exercici 2: Zones operatives amb union-find

Rutalia té n zones (0..n−1) i una llista de passos oberts passos = [(a, b), ...]. Escriu components(n, passos) que retorni quants grups de zones mútuament abastables hi ha, fent servir la classe UnionFind de la lliçó. Exemple: components(6, [(0,1), (1,2), (4,5)]) → 3 (grups {0,1,2}, {3}, {4,5}).

Exercici 3: Comptador de prefixos al trie

Amplia la classe Trie amb un mètode comptar_prefix(prefix) que retorni quantes adreces comencen pel prefix, en O(L) —sense recórrer el subarbre—. Pista: emmagatzema a cada node un comptador que s'incrementi en inserir.

Solucions

Solució 1

import heapq

def despatxar(comandes, k):
    heap = list(comandes)
    heapq.heapify(heap)                              # O(n)
    return [heapq.heappop(heap) for _ in range(k)]   # k extraccions: O(k log n)

Complexitat: O(n + k·log n). Ordenar la llista completa és O(n log n). Amb n = 10⁶ i k = 10: ~10⁶ + 10·20 operacions davant de ~2·10⁷; el heap guanya amb claredat perquè no paga per ordenar allò que no es despatxa. (Encara més directe: heapq.nsmallest(k, comandes) fa essencialment això.) Si k ≈ n, les dues opcions convergeixen a O(n log n) i ordenar és més simple.

Solució 2

def components(n, passos):
    uf = UnionFind(n)
    grups = n                       # al principi, cada zona és el seu propi grup
    for a, b in passos:
        if uf.union(a, b):          # union retorna True només si fusiona
            grups -= 1              # cada fusió real redueix els grups en 1
    return grups

print(components(6, [(0, 1), (1, 2), (4, 5)]))   # 3

Cost: O(n + m·α(n)) per a m passos — pràcticament lineal. El truc de comptar amb el valor de retorn d'union estalvia un recorregut final cercant arrels diferents. Error comú: comptar cada crida a union com a fusió sense comprovar si ja estaven connectades.

Solució 3

    def inserir(self, paraula):
        node = self.arrel
        for ch in paraula:
            node = node.setdefault(ch, {})
            node["#"] = node.get("#", 0) + 1   # nre. de paraules que passen per aquí
        node[self.FI] = True

    def comptar_prefix(self, prefix):
        node = self.arrel
        for ch in prefix:
            if ch not in node:
                return 0
            node = node[ch]
        return node.get("#", 0)

Cada node porta quantes paraules travessen aquest prefix; comptar_prefix només baixa L nivells → O(L), independent del nombre d'adreces. (Amb aquesta variant, les claus "#" i FI conviuen amb els caràcters fills; el recorregut d'amb_prefix ha de saltar-se totes dues. Si s'insereixen paraules repetides, el comptador les compta totes — decideix si això és el que vols.)

Conclusió

Tanquem el primer mòdul amb la caixa d'eines completa. Les estructures bàsiques (array, llista enllaçada, pila, cua) responen preguntes posicionals; les avançades responen preguntes de més valor: el heap lliura l'element més prioritari en O(log n) i és el motor de les cues de prioritat de heapq; la taula de hash (dict/set) dona pertinença i indexació en O(1) mitjà a canvi de renunciar a l'ordre; el union-find amb compressió de camins i unió per rang manté grups que es fusionen en temps pràcticament constant; i el trie organitza cadenes per prefixos, fent que l'autocompletat sigui independent de la mida del nomenclàtor. A Rutalia, cadascuna resol una pregunta concreta del negoci: prioritzar comandes urgents, localitzar una comanda a l'instant, saber si dues zones segueixen connectades i suggerir adreces mentre es tecleja. I hem deixat dues llavors plantades: el heap és la peça que farà eficient Dijkstra (lliçó 03-03) i el union-find, Kruskal (lliçó 03-04).

Amb això acaba la introducció: sabem expressar costos (01-01), calcular-los (01-02), dissenyar amb recursió i programació dinàmica (01-03) i recolzar-nos en les estructures adequades (01-04). Al mòdul 2, Algorismes d'Optimització, passem d'analitzar a decidir: Rutalia ja no preguntarà "quant costa aquesta operació?" sinó "quina és la millor assignació de recursos possible?" — començant per la programació lineal (02-01) i seguint amb optimització combinatòria, backtracking i branch and bound, algorismes genètics i colònies de formigues.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats