El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

Totes les cues que hem construït fins ara comparteixen una regla: surt el més antic. Però a TaskFlow hi ha moments en què aquesta regla és injusta al revés: una tasca de prioritat 1 ("el servidor ha caigut") no pot esperar darrere de vint tasques rutinàries que van arribar abans. Necessitem una cua on desencuar signifiqui "dona'm el més prioritari", no "dona'm el més antic". Aquest TAD és la cua de prioritat, i tanca el segon pont del mòdul 3: la PilaAmbMinim podia consultar l'element mínim en O(1), però no extreure'l; avui aprendrem a extreure'l. Compararem dues implementacions honestes —llista no ordenada i llista ordenada, reutilitzant l'inserir_ordenat del mòdul 2—, entendrem els seus costos enfrontats, i usarem l'eina professional de Python, heapq, com a caixa negra, amb una atenció especial a un detall que separa el codi correcte del codi traïdor: els empats i l'estabilitat.

Contingut

El TAD cua de prioritat
Implementació 1: llista no ordenada
Implementació 2: llista ordenada (reutilitzant inserir_ordenat)
Taula comparativa i l'anunci del monticle
heapq: la caixa negra professional
Empats i estabilitat: el truc del comptador
TaskFlow: la safata d'urgències

El TAD cua de prioritat

El contracte s'assembla al de la cua FIFO, però canvia la promesa central:

Operació	Cua FIFO	Cua de prioritat
`encuar(element)`	Entra pel final	Entra "on correspongui"
`desencuar()`	Surt el més antic	Surt el més prioritari
`front()`	Consulta el més antic	Consulta el més prioritari
`esta_buida()` / `mida()`	Igual	Igual

A TaskFlow, prioritat 1 és la màxima, així que "el més prioritari" és el de menor número de prioritat: la nostra cua de prioritat és de mínims (min-priority queue). És un conveni freqüent (pensa en "prioritat 1" en suport tècnic) i encaixa de sèrie amb les eines de Python, que també treballen amb mínims.

Fixa't que el TAD no diu res de com s'aconsegueix: només promet que desencuar retorna el mínim. Com sempre des del mòdul 1, un mateix contracte admet implementacions amb costos molt diferents — i aquesta vegada la tensió entre elles és especialment instructiva: es pot pagar en entrar o pagar en sortir, però amb llistes es paga.

Implementació 1: llista no ordenada

L'estratègia mandrosa: encuar és deixar anar l'element al final, sense cap ordre; desencuar és buscar el mínim i treure'l.

class CuaPrioritatNoOrdenada:
    """Encuar O(1); desencuar O(n): busca el minim cada vegada."""

    def __init__(self):
        self._elements = []           # parells (prioritat, tasca), sense ordre

    def encuar(self, prioritat, tasca):
        self._elements.append((prioritat, tasca))      # O(1): al final i llestos

    def desencuar(self):
        if self.esta_buida():
            raise IndexError("desencuar sobre una cua buida")
        # Buscar la posicio del minim: recorregut complet, O(n)
        millor = 0
        for i in range(1, len(self._elements)):
            if self._elements[i][0] < self._elements[millor][0]:
                millor = i
        return self._elements.pop(millor)[1]           # pop(i) tambe O(n)

    def front(self):
        if self.esta_buida():
            raise IndexError("front sobre una cua buida")
        return min(self._elements, key=lambda parell: parell[0])[1]   # O(n)

    def esta_buida(self):
        return len(self._elements) == 0

    def mida(self):
        return len(self._elements)

Anàlisi: encuar és O(1) —imbatible—, però desencuar recorre tota la llista per localitzar el mínim (O(n)) i, a sobre, l'extreu amb pop(millor), que desplaça els elements posteriors (una altra vegada O(n), vell conegut del mòdul 1). Quan compensa? Quan s'encua moltíssim i es desencua molt poc: per exemple, si acumules milers de candidats però només n'extrauràs uns quants.

Implementació 2: llista ordenada (reutilitzant `inserir_ordenat`)

L'estratègia previsora: mantenir la col·lecció sempre ordenada per prioritat, de manera que el mínim estigui a punt al front. Quan al mòdul 2 vam escriure inserir_ordenat sobre la LlistaEnllacada, vam anunciar que era "un pont cap a les cues de prioritat". Aquest és el moment de creuar-lo: si la llista enllaçada es manté ordenada ascendentment per prioritat, el més urgent és al cap, i extreure'l és l'eliminar_del_principi O(1) de la lliçó 04-02.

class CuaPrioritatOrdenada:
    """Encuar O(n) (insercio ordenada); desencuar O(1) (el cap)."""

    def __init__(self):
        self._elements = LlistaEnllacada()   # ordenada ascendent per prioritat

    def encuar(self, prioritat, tasca):
        # inserir_ordenat del modul 2, guardant parells (prioritat, tasca):
        # recorre fins al primer node amb prioritat MES GRAN i s'insereix abans.
        nou = Node((prioritat, tasca))
        if (self._elements.cap is None
                or prioritat < self._elements.cap.dada[0]):
            nou.seguent = self._elements.cap               # nou cap
            self._elements.cap = nou
            if nou.seguent is None:
                self._elements.cua = nou
        else:
            actual = self._elements.cap
            # Avancar mentre el seguent existeixi i no sigui menys urgent.
            # ULL al <=: els empats queden DARRERE dels ja existents
            # (aixo preserva l'ordre d'arribada entre iguals: estabilitat).
            while (actual.seguent is not None
                   and actual.seguent.dada[0] <= prioritat):
                actual = actual.seguent
            nou.seguent = actual.seguent
            actual.seguent = nou
            if nou.seguent is None:
                self._elements.cua = nou
        self._elements.mida += 1

    def desencuar(self):
        if self.esta_buida():
            raise IndexError("desencuar sobre una cua buida")
        return self._elements.eliminar_del_principi()[1]   # O(1)

    def front(self):
        if self.esta_buida():
            raise IndexError("front sobre una cua buida")
        return self._elements.cap.dada[1]                  # O(1)

    def esta_buida(self):
        return self._elements.mida == 0

    def mida(self):
        return self._elements.mida

Ara els costos s'inverteixen: encuar recorre la llista fins a trobar el forat (O(n)), però desencuar i front són O(1). Quan compensa? Quan desencues i consultes molt més del que encues — per exemple, un panell que consulta constantment "quina és la propera urgència?".

Detall fi que hem deixat comentat al codi: el <= del bucle fa que una tasca nova amb la mateixa prioritat que d'altres d'existents es col·loqui darrere d'elles. Entre iguals, ordre d'arribada: guardarem aquest concepte —estabilitat— per a la secció d'empats, perquè amb heapq caldrà guanyar-se'l a pols.

Taula comparativa i l'anunci del monticle

Implementació	`encuar`	`desencuar`	`front`	Quan triar-la?
Llista no ordenada	O(1)	O(n)	O(n)	Moltes insercions, poques extraccions
Llista ordenada (`inserir_ordenat`)	O(n)	O(1)	O(1)	Poques insercions, moltes extraccions/consultes
Monticle (heap) — mòdul 6	O(log n)	O(log n)	O(1)	El cas general: barreja de totes dues

La taula revela un patró que veuràs una vegada i una altra en estructures de dades: dues solucions simètriques que paguen O(n) en operacions oposades, i una tercera estructura més sofisticada que equilibra: ni O(1) ni O(n), sinó O(log n) en totes dues. Perquè et facis una idea del que significa: amb n = 1.000.000, O(n) són un milió de passos i O(log n) en són uns 20. Aquesta estructura és el monticle (heap), un arbre amb una propietat d'ordre molt astuta... i per això viu al mòdul 6 (lliçó 06-07), després que haguem après arbres. Aquí no l'obrirem: el farem servir.

`heapq`: la caixa negra professional

Python porta el monticle de sèrie al mòdul heapq. L'usarem com a caixa negra: sabem què promet (mínim a fora, O(log n) per operació) sense mirar encara com ho aconsegueix. És exactament la disciplina TAD del mòdul 1 aplicada a una biblioteca real.

heapq no defineix cap classe: ofereix funcions que operen sobre una list normal a la qual mantenen la propietat de monticle:

import heapq

pendents = []                         # una list corrent fara de monticle

heapq.heappush(pendents, 3)           # encuar: O(log n)
heapq.heappush(pendents, 1)
heapq.heappush(pendents, 2)

print(pendents[0])                    # 1 → el minim SEMPRE es a [0] (front)
print(heapq.heappop(pendents))        # 1 → desencuar: extreu el minim, O(log n)
print(heapq.heappop(pendents))        # 2
print(heapq.heappop(pendents))        # 3

Regles de la caixa negra:

heappush(llista, element) = encuar; heappop(llista) = desencuar (el mínim); llista[0] = front; len(llista) = mida.
La llista només s'ha de tocar amb funcions de heapq (o llegir-ne el [0]). Un append o un sort pel teu compte trenca la propietat interna i el mínim deixa d'estar garantit.
Curiositat que connecta amb el mòdul 6: encara que l'interior de pendents és una list aparentment desordenada (imprimeix-la!), la seva estructura codifica un arbre. Que un array pugui "ser" un arbre és una de les idees boniques que hi desvelarem.

I si els elements no són números solts? heapq compara els elements entre si amb <. Amb tuples, Python compara component a component, així que el costum és encuar tuples el primer camp de les quals sigui la prioritat: (prioritat, tasca). I aquí apareix una trampa seriosa.

Empats i estabilitat: el truc del comptador

Intentem encuar tasques (els nostres dict) amb la seva prioritat:

import heapq

urgencies = []
t1 = {"id": 1, "titol": "Reiniciar el servidor", "prioritat": 1, "estat": "pendent"}
t2 = {"id": 2, "titol": "Avisar els clients", "prioritat": 1, "estat": "pendent"}

heapq.heappush(urgencies, (t1["prioritat"], t1))
heapq.heappush(urgencies, (t2["prioritat"], t2))   # TypeError!

TypeError: '<' not supported between instances of 'dict' and 'dict'. Per què? Totes dues tuples empaten al primer camp (1 == 1), així que Python passa a comparar el segon... i els dict no saben comparar-se amb <. L'empat trenca el programa.

I encara que els elements fossin comparables, quedaria un problema més subtil: entre dues tasques de prioritat 1, quina ha de sortir primer? El que és just —i el que espera qualsevol usuari— és la que va arribar abans: a igual prioritat, FIFO. Aquesta propietat es diu estabilitat, i heapq per si sol no la garanteix (l'ordre intern del monticle no recorda arribades).

El truc canònic resol totes dues coses alhora: encuar tuples de tres camps, (prioritat, comptador, tasca), on comptador és un enter que creix amb cada inserció:

Si les prioritats empaten, es compara el comptador, que mai no empata → mai no s'arriba a comparar els dict (adeu TypeError).
El comptador menor correspon a l'arribada més antiga → els empats surten per ordre d'arribada (estabilitat garantida).

import heapq
from itertools import count

urgencies = []
comptador = count()       # count() genera 0, 1, 2, ... un de nou a cada next()

heapq.heappush(urgencies, (t1["prioritat"], next(comptador), t1))
heapq.heappush(urgencies, (t2["prioritat"], next(comptador), t2))   # ara si

prioritat, _, tasca = heapq.heappop(urgencies)
print(tasca["titol"])     # "Reiniciar el servidor": va arribar abans que el seu empat

Aquest patró (prioritat, comptador, element) és tan estàndard que el trobaràs tal qual a la documentació oficial de Python i en codi de producció. Memoritza'l com es memoritza un idiom.

TaskFlow: la safata d'urgències

Empaquetem el patró a la peça de TaskFlow d'aquesta lliçó: la safata d'urgències, on s'aboquen tasques de qualsevol procedència i sempre s'atén la més urgent (recorda: prioritat 1 = màxima), amb empats resolts per arribada:

import heapq
from itertools import count

class SafataUrgencies:
    """Cua de prioritat de tasques de TaskFlow sobre heapq.

    desencuar() retorna la tasca de menor numero de prioritat;
    a igual prioritat, la que es va encuar abans (estable).
    """

    def __init__(self):
        self._monticle = []
        self._comptador = count()

    def encuar(self, tasca):
        entrada = (tasca["prioritat"], next(self._comptador), tasca)
        heapq.heappush(self._monticle, entrada)           # O(log n)

    def desencuar(self):
        if self.esta_buida():
            raise IndexError("desencuar sobre una safata buida")
        return heapq.heappop(self._monticle)[2]           # O(log n); [2] = tasca

    def front(self):
        if self.esta_buida():
            raise IndexError("front sobre una safata buida")
        return self._monticle[0][2]                       # O(1)

    def esta_buida(self):
        return len(self._monticle) == 0

    def mida(self):
        return len(self._monticle)


# --- Us ---
safata = SafataUrgencies()
safata.encuar({"id": 4, "titol": "Actualitzar la documentacio",
               "prioritat": 3, "estat": "pendent"})
safata.encuar({"id": 5, "titol": "Servidor caigut",
               "prioritat": 1, "estat": "pendent", "assignada_a": "anna"})
safata.encuar({"id": 6, "titol": "Client sense acces",
               "prioritat": 1, "estat": "pendent", "assignada_a": "bruno"})
safata.encuar({"id": 7, "titol": "Revisar els estils CSS",
               "prioritat": 2, "estat": "pendent"})

while not safata.esta_buida():
    tasca = safata.desencuar()
    print(f"prioritat {tasca['prioritat']}: {tasca['titol']}")

# prioritat 1: Servidor caigut          ← empat a 1: surt la que va arribar abans
# prioritat 1: Client sense acces
# prioritat 2: Revisar els estils CSS
# prioritat 3: Actualitzar la documentacio

La sortida resumeix la lliçó sencera: mana la prioritat, no l'arribada (la tasca 5 avança la 4); i entre empats mana l'arribada (la 5 abans que la 6). El monticle fa totes dues coses en O(log n) per operació, i al mòdul 6 obrirem per fi la caixa per veure l'arbre que ho fa possible.

Errors Comuns i Consells

Encuar (prioritat, tasca) sense comptador: funciona a les proves... fins al primer empat amb dicts, i llavors TypeError en producció. Usa sempre (prioritat, comptador, element) quan l'element no sigui comparable (i encara que ho sigui: hi guanyes estabilitat).
Confondre el sentit de la prioritat: heapq extreu el mínim. Amb el nostre conveni (1 = màxima) encaixa directe; si el teu conveni fos "número més gran = més urgent", hauries d'encuar (-prioritat, comptador, tasca). Documenta el conveni del projecte i no els barregis.
Tocar la llista del monticle per fora: un llista.append(x) o llista.sort() sobre el monticle trenca el seu invariant intern silenciosament: no falla al moment, falla després, retornant mínims incorrectes. La llista del monticle és territori exclusiu de heapq (per això SafataUrgencies l'amaga darrere de _).
Reordenar després de canviar la prioritat d'una tasca ja encuada: mutar tasca["prioritat"] no recol·loca la seva entrada al monticle. El patró professional és encuar una entrada nova i marcar la vella com a invalidada (o reconstruir la cua si és petita). Treballarem aquesta idea als projectes del mòdul 8.
Consell: si dubtes entre llista ordenada, no ordenada o heapq, compta operacions: dominen les insercions, les extraccions o van a la par? La taula comparativa d'aquesta lliçó és literalment una guia de decisió; tingues-la a mà.

Exercicis

Exercici 1: predir amb empats

Sense executar, indica en quin ordre surten els títols si s'encuen en una SafataUrgencies aquestes tasques (en aquest ordre) i després es desencua tot: ("Backup", 2), ("Incendi", 1), ("Informe", 2), ("Rescat", 1). Justifica cada posició amb la regla corresponent (prioritat o estabilitat).

Exercici 2: `desencuar` estable a la llista NO ordenada

La CuaPrioritatNoOrdenada d'aquesta lliçó no és estable: davant d'un empat, retorna el primer que troba, cosa que només és correcta per accident. Modifica desencuar perquè la cerca del mínim usi < estricte (no <=) en comparar, i raona per què això —atès que append afegeix al final— garanteix que entre empats surt el més antic.

Exercici 3: fusionar dues safates

Els equips "web" i "mòbil" de TaskFlow mantenen safates d'urgències separades i es fusionen en un sol equip. Escriu una funció fusionar(safata_a, safata_b) que retorni una SafataUrgencies nova amb totes les tasques de totes dues, conservant l'ordre per prioritat. Es conserva també l'estabilitat entre safates? Raona la resposta.

Solucions

Solució 1: Ordre de sortida: Incendi, Rescat, Backup, Informe.

Incendi (prioritat 1): mínim global.
Rescat (prioritat 1): empata amb Incendi, però Incendi va arribar abans (comptador menor) → estabilitat.
Backup (prioritat 2): ja no en queda cap de menor que 2; empata amb Informe i va arribar abans.
Informe (prioritat 2): últim per estabilitat.

Solució 2:

def desencuar(self):
    if self.esta_buida():
        raise IndexError("desencuar sobre una cua buida")
    millor = 0
    for i in range(1, len(self._elements)):
        if self._elements[i][0] < self._elements[millor][0]:   # < ESTRICTE
            millor = i
    return self._elements.pop(millor)[1]

Raonament: append col·loca cada element nou darrere dels anteriors, així que dins de la llista els empats estan en ordre d'arribada. La cerca amb < estricte només canvia de candidat davant d'un element estrictament millor; davant d'un empat es queda amb el que ja tenia, que per recórrer d'esquerra a dreta és el d'índex menor = el més antic. Amb <= passaria el contrari: es quedaria l'últim empat, invertint l'ordre d'arribada.

Solució 3:

def fusionar(safata_a, safata_b):
    resultat = SafataUrgencies()
    for safata in (safata_a, safata_b):
        while not safata.esta_buida():
            resultat.encuar(safata.desencuar())
    return resultat

L'ordre per prioritat es conserva sempre: cada tasca es reencua amb la seva prioritat i el monticle nou les ordenarà. L'estabilitat es conserva dins de cada safata (desencuem en ordre estable i reencuem en aquest mateix ordre, amb comptadors nous creixents), però entre safates no hi ha garantia històrica: totes les tasques de safata_a reben comptadors menors que les de safata_b, de manera que en els empats entre safates sempre guanya la safata a, no la tasca que realment va arribar abans en el temps. Per a una fusió històricament justa caldria haver guardat una marca de temps global a cada tasca. Nota la millora respecte de versions ingènues: la funció consumeix les safates originals; si les volguessis conservar, hauries de reencuar també a les originals (rotació) o exposar-ne una còpia.

Conclusió

La cua de prioritat canvia la promesa del desencuar: ja no surt el més antic, sinó el més urgent — a TaskFlow, el de menor número de prioritat. Hem vist el dilema de les implementacions amb llista (no ordenada: encuar O(1) / desencuar O(n); ordenada amb inserir_ordenat: encuar O(n) / desencuar O(1)), i hem usat la solució equilibrada de la biblioteca estàndard, heapq, amb l'idiom (prioritat, comptador, tasca) que evita el TypeError dels empats i garanteix estabilitat: a igual urgència, ordre d'arribada. El monticle que hi ha dins de heapq —i per què aconsegueix O(log n)— és cita pendent per a la lliçó 06-07, quan sabrem d'arbres. Ens queda un pont del mòdul 3 per creuar, el primer de tots: aquell HistorialAmbLimit que necessitava eficiència pels dos extrems alhora. L'estructura que ho aconsegueix —la cua doble o deque— i la joia de la biblioteca estàndard que la implementa, collections.deque, ens esperen a la propera lliçó.

Cues de Prioritat

Contingut

El TAD cua de prioritat

Implementació 1: llista no ordenada

Implementació 2: llista ordenada (reutilitzant `inserir_ordenat`)

Taula comparativa i l'anunci del monticle

`heapq`: la caixa negra professional

Empats i estabilitat: el truc del comptador

TaskFlow: la safata d'urgències

Errors Comuns i Consells

Exercicis

Exercici 1: predir amb empats

Exercici 2: `desencuar` estable a la llista NO ordenada

Exercici 3: fusionar dues safates

Solucions

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

Cues de Prioritat

Contingut

El TAD cua de prioritat

Implementació 1: llista no ordenada

Implementació 2: llista ordenada (reutilitzant inserir_ordenat)

Taula comparativa i l'anunci del monticle

heapq: la caixa negra professional

Empats i estabilitat: el truc del comptador

TaskFlow: la safata d'urgències

Errors Comuns i Consells

Exercicis

Exercici 1: predir amb empats

Exercici 2: desencuar estable a la llista NO ordenada

Exercici 3: fusionar dues safates

Solucions

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

Implementació 2: llista ordenada (reutilitzant `inserir_ordenat`)

`heapq`: la caixa negra professional

Exercici 2: `desencuar` estable a la llista NO ordenada