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

HOME

Hora de saldar el deute més antic del curs. Al mòdul 4, la SafataUrgencies de TaskFlow despatxava sempre la tasca més prioritària usant heapq com a caixa negra: hi ficàvem tuples (prioritat, comptador, tasca) i sortien en ordre, "per art de màgia i en O(log n)", amb la promesa d'obrir la caixa en aquest mòdul. Ja tens totes les peces: saps què és un arbre binari complet (06-02), coneixes la representació en array amb índexs 2i+1/2i+2 (06-02) i entens per què les operacions O(altura) són ràpides si l'altura és logarítmica. El monticle (heap) combina les tres idees amb una relaxació genial: no manté l'ordre total de l'ABC — només garanteix que cada pare és menor o igual que els seus fills — i amb aquest contracte mínim aconsegueix inserir i extreure el mínim en O(log n) sobre un simple array, sense nodes ni referències. En aquesta lliçó implementaràs el monticle complet, reconstruiràs la SafataUrgencies sobre ell i tancaràs la taula comparativa de les cues de prioritat.

Contingut

La propietat de monticle: ordre parcial, no total
La forma: arbre complet = array sense forats
Inserir: flotar (sift-up)
Extreure el mínim: enfonsar (sift-down)
La classe Monticle completa
SafataUrgencies 2.0: la caixa negra, oberta
Bonus: heapify en O(n), heapsort i el max-heap

La propietat de monticle: ordre parcial, no total

Un min-heap és un arbre binari que compleix dues condicions:

Propietat de forma: és un arbre binari complet (tots els nivells plens llevat de l'últim, omplert d'esquerra a dreta — 06-02).
Propietat de monticle: tot pare és menor o igual que cadascun dels seus fills.

I res més. Compara'l amb l'ABC, perquè el contrast és la clau de la lliçó:

graph TD
    subgraph "Min-heap vàlid"
        A((1)) --> B((3))
        A --> C((2))
        B --> D((7))
        B --> E((4))
        C --> F((5))
        C --> G((9))
    end

	ABC (06-04)	Min-heap
Regla	esquerra < node < dreta	pare ≤ fills (sense distingir costats)
Tipus d'ordre	total: l'inordre ho llista tot ordenat	parcial: només garanteix el camí arrel-fulla
On és el mínim?	fulla més a l'esquerra (O(altura))	l'arrel, sempre (O(1))
Cercar un valor qualsevol?	O(altura)	O(n) — no hi ha pistes d'on és
Intervals, successor, llistat ordenat?	sí	no
Forma	la que surti (per això existeix l'AVL)	completa per definició: altura ⌊log₂ n⌋ gratis

Mira el diagrama: el 3 és a l'esquerra del 2 i a ningú no li importa — entre germans no hi ha cap ordre. Un heap és un ABC que ha renunciat a gairebé tot: no sap llistar ordenat, ni respondre intervals, ni trobar un element. A canvi d'aquesta renúncia, guanya dues coses que l'ABC no té: el mínim a l'arrel sempre, i equilibri perfecte per definició (la forma completa no és negociable, així que no hi ha degeneració possible ni cal cap AVL que la vigili). És l'especialització perfecta per a una única pregunta: "quin és el més urgent?" — exactament la pregunta d'una cua de prioritat. Regla mental per triar: necessites tots els elements en ordre en qualsevol moment? ABC/AVL. Només el següent més petit, un cop i un altre? Heap.

La forma: arbre complet = array sense forats

Aquí germina la llavor plantada a 06-02: com que el heap és sempre un arbre complet, viu perfecte en un array sense malgastar ni una casella — res de NodeBinari, ni referències, ni memòria extra. El diagrama anterior és, en memòria, això:

monticle = [1, 3, 2, 7, 4, 5, 9]
#  índexs:  0  1  2  3  4  5  6

Amb l'aritmètica de 06-02 com a única navegació: fills d'i a 2i+1 i 2i+2, pare a (i-1)//2. Verifica la propietat sobre l'array: monticle[1] = 3 ≥ monticle[0] = 1 (pare a (1-1)//2 = 0), monticle[5] = 5 ≥ monticle[2] = 2... La propietat de monticle, traduïda a array: arr[i] >= arr[(i-1)//2] per a tot i > 0.

Quan al mòdul 4 vam escriure heapq.heappush(safata, ...) sobre una llista de Python i et vam demanar fe: això és el que hi havia. heapq no és una estructura: són funcions que mantenen aquesta propietat sobre una llista normal. Imprimeix un heap de heapq i veuràs l'array de dalt — desordenat a simple vista, ordenat segons el contracte del heap.

Inserir: flotar (sift-up)

Per inserir cal conservar les dues propietats. L'estratègia: garantir la forma primer i reparar l'ordre després.

Col·loca l'element nou a l'única posició que manté l'arbre complet: el final de l'array (el primer forat de l'últim nivell).
Pot ser que ara sigui menor que el seu pare, violant la propietat. Es corregeix fent-lo flotar (sift-up): mentre sigui menor que el seu pare, intercanvia'ls i puja.

Inserim el 0 al heap de l'exemple, amb traça completa:

[1, 3, 2, 7, 4, 5, 9, 0]      el 0 entra a i=7; el seu pare: (7-1)//2 = 3, val 7
        0 < 7: intercanvi  →  [1, 3, 2, 0, 4, 5, 9, 7]   ara i=3, pare i=1 (val 3)
        0 < 3: intercanvi  →  [1, 0, 2, 3, 4, 5, 9, 7]   ara i=1, pare i=0 (val 1)
        0 < 1: intercanvi  →  [0, 1, 2, 3, 4, 5, 9, 7]   i=0: és l'arrel, fi

graph TD
    subgraph "1. El 0 entra al final"
        A((1)) --> B((3))
        A --> C((2))
        B --> D((7))
        B --> E((4))
        C --> F((5))
        C --> G((9))
        D --> H((0))
    end
    subgraph "2. Després de flotar fins a l'arrel"
        A2((0)) --> B2((1))
        A2 --> C2((2))
        B2 --> D2((3))
        B2 --> E2((4))
        C2 --> F2((5))
        C2 --> G2((9))
        D2 --> H2((7))
    end

Fixa't en el que el 0 no ha tocat: el subarbre del 2 ni se n'ha assabentat. Flotar només recorre el camí del node nou cap a l'arrel — com a molt l'altura de l'arbre, que en un arbre complet és ⌊log₂ n⌋ clavats. Inserció: O(log n), garantit sense rotacions ni vigilants.

Extreure el mínim: enfonsar (sift-down)

El mínim és l'arrel (arr[0]), però arrencar-la deixaria un forat a dalt — i els arrays odien els forats a l'índex 0 (recordes el desencuar O(n) de la cua sobre llista, al mòdul 4?). El truc mirall de l'anterior — forma primer, ordre després:

Guarda l'arrel (és el resultat). Mou l'últim element de l'array a l'arrel — la forma torna a ser correcta, encongida per on toca.
Aquest element probablement és massa gran per al cim: enfonsa'l (sift-down) — mentre sigui major que algun dels seus fills, intercanvia'l amb el menor dels dos i baixa.

Extraiem del heap resultant [0, 1, 2, 3, 4, 5, 9, 7]:

surt el 0; l'últim (7) puja a l'arrel     →  [7, 1, 2, 3, 4, 5, 9]
   fills del 7 (i=0): 1 (i=1) i 2 (i=2); el menor és l'1
   7 > 1: intercanvi                      →  [1, 7, 2, 3, 4, 5, 9]
   fills del 7 (i=1): 3 (i=3) i 4 (i=4); el menor és el 3
   7 > 3: intercanvi                      →  [1, 3, 2, 7, 4, 5, 9]
   fills del 7 (i=3): només el 7... no en té (2·3+1 = 7 ≥ len): és fulla, fi

Per què amb el menor dels dos fills? Perquè l'elegit es convertirà en pare de l'altre: si puéssim pujar el major, violaríem la propietat a l'acte. És l'error clàssic d'implementació — amb dos fills 3 i 4, pujar el 4 deixa 4 > 3 com a pare del 3.

Cost: de nou el camí de l'arrel a una fulla com a màxim — O(log n). I la seqüència d'extraccions successives retorna els elements en ordre ascendent: 0, 1, 2, 3... cada extracció reorganitza just el necessari perquè el nou mínim aflori al cim.

La classe `Monticle` completa

Tot junt, en una classe amb la interfície d'una cua de prioritat:

class Monticle:
    """Min-heap sobre una llista de Python. Els elements han de ser comparables."""

    def __init__(self):
        self.dades = []

    def __len__(self):
        return len(self.dades)

    def veure_minim(self):
        """El mínim sense extreure'l. O(1): és l'arrel."""
        return self.dades[0] if self.dades else None

    def inserir(self, element):
        """Afegir al final i flotar. O(log n)."""
        self.dades.append(element)
        self._flotar(len(self.dades) - 1)

    def extreure_minim(self):
        """Treure l'arrel, pujar l'últim i enfonsar-lo. O(log n)."""
        if not self.dades:
            return None
        minim = self.dades[0]
        ultim = self.dades.pop()           # O(1): treure pel final
        if self.dades:                     # si queda algú, ocupa el cim i s'enfonsa
            self.dades[0] = ultim
            self._enfonsar(0)
        return minim

    def _flotar(self, i):
        while i > 0:
            pare = (i - 1) // 2
            if self.dades[i] < self.dades[pare]:
                self.dades[i], self.dades[pare] = self.dades[pare], self.dades[i]
                i = pare                   # continuar pujant des de la nova posició
            else:
                break                      # el pare ja és menor o igual: al seu lloc

    def _enfonsar(self, i):
        n = len(self.dades)
        while True:
            esq, dre = 2 * i + 1, 2 * i + 2
            menor = i
            if esq < n and self.dades[esq] < self.dades[menor]:
                menor = esq
            if dre < n and self.dades[dre] < self.dades[menor]:
                menor = dre                # el menor dels tres: pare, esq, dre
            if menor == i:
                break                      # ja és menor que tots dos fills: al seu lloc
            self.dades[i], self.dades[menor] = self.dades[menor], self.dades[i]
            i = menor                      # continuar baixant des de la nova posició

Detalls que mereixen segona lectura:

_enfonsar calcula menor entre tres candidats (el mateix node i els seus fills existents): així l'intercanvi és sempre amb el menor dels fills i les comprovacions esq < n cobreixen els nodes amb un sol fill o cap.
A extreure_minim, el cas "quedava un sol element" surt gratis: pop() el treu, self.dades queda buida i no s'enfonsa res.
Provem que la màgia del mòdul 4 ja no és màgia:

m = Monticle()
for x in [5, 3, 8, 1, 9, 2]:
    m.inserir(x)
print(m.dades)          # [1, 3, 2, 5, 9, 8] — l'array-heap, a la vista
while len(m):
    print(m.extreure_minim(), end=" ")   # 1 2 3 5 8 9 — ascendent

Això és, línia a línia de comportament, el que heapq.heappush i heapq.heappop feien al mòdul 4 (amb la llista exposada en lloc d'encapsulada — decisió de disseny de Python, TAD vs implementació del mòdul 1). Caixa negra: oberta.

`SafataUrgencies` 2.0: la caixa negra, oberta

Reconstruïm la SafataUrgencies del mòdul 4 sobre el nostre monticle, amb la seva mateixa interfície i el seu mateix truc de les tuples (prioritat, comptador, tasca) — que ara entens del tot: les tuples es comparen element a element, així que el heap ordena per prioritat; el comptador d'itertools.count desempata FIFO entre iguals i evita que la comparació arribi al dict (els diccionaris no es comparen amb <; sense comptador, dues tasques d'igual prioritat rebentarien amb TypeError).

from itertools import count

class SafataUrgencies:
    """Cua de prioritat de TaskFlow. Prioritat 1 = màxima.
    Mateixa interfície que al mòdul 4; motor propi."""

    def __init__(self):
        self._heap = Monticle()
        self._comptador = count()          # desempat FIFO i escut anti-TypeError

    def arriba(self, tasca):
        self._heap.inserir((tasca["prioritat"], next(self._comptador), tasca))

    def seguent(self):
        """La tasca més urgent (i més antiga entre iguals), o None."""
        entrada = self._heap.extreure_minim()
        return entrada[2] if entrada else None

    def urgent_a_la_vista(self):
        entrada = self._heap.veure_minim()
        return entrada[2] if entrada else None

safata = SafataUrgencies()
safata.arriba({"id": "T-11", "titol": "Informe setmanal", "prioritat": 3, "estat": "pendent"})
safata.arriba({"id": "T-12", "titol": "Servidor caigut", "prioritat": 1, "estat": "pendent"})
safata.arriba({"id": "T-13", "titol": "Revisar PR", "prioritat": 2, "estat": "pendent"})
safata.arriba({"id": "T-14", "titol": "Base de dades lenta", "prioritat": 1, "estat": "pendent"})

print(safata.seguent()["id"])   # T-12  (prioritat 1, ha arribat abans que T-14)
print(safata.seguent()["id"])   # T-14  (prioritat 1)
print(safata.seguent()["id"])   # T-13  (prioritat 2)

I la taula que el mòdul 4 va deixar a mitges, ara completa — les tres implementacions de cua de prioritat, cara a cara:

Implementació (mòdul)	`arriba` (inserir)	`seguent` (extreure mín.)	`urgent_a_la_vista`
`CuaPrioritatNoOrdenada` (4)	O(1)	O(n) — cercar el mínim	O(n)
`CuaPrioritatOrdenada` (4)	O(n) — `inserir_ordenat`	O(1)	O(1)
Monticle (6)	O(log n)	O(log n)	O(1)

Les dues primeres pagaven O(n) en una de les dues operacions — mantenien massa poc ordre (cap) o massa (total). El heap és l'equilibri exacte: l'ordre just per respondre "el següent?" ràpid, ni una gota més. Amb 10 000 tasques i trànsit constant d'arribades i despatxos, és la diferència entre milers d'operacions per esdeveniment i ~13. Aquesta idea — pagar només per l'ordre que de debò consumeixes — és de les més rendibles que t'emportes del curs.

Bonus: heapify en O(n), heapsort i el max-heap

Heapify. Convertir una llista de n elements en heap? Inserir-los d'un en un costa O(n log n). Però hi ha un camí millor, i a 06-02 (exercici 2) en vas veure la peça clau: en un array-heap, tots els índexs des de n//2 fins al final són fulles — i una fulla ja és un mini-heap vàlid. N'hi ha prou, doncs, de recórrer els nodes interns de darrere cap endavant (n//2 - 1 → 0) enfonsant cadascun: quan li toca a un node, els seus dos subarbres ja són heaps, i enfonsar-lo fon els tres en un. El compte sorprèn: la meitat dels nodes (fulles) treballen 0, un quart enfonsa 1 nivell, un vuitè 2... la suma convergeix a O(n), no O(n log n) — gairebé tots els nodes són a baix i tenen poc a enfonsar. És el que fa heapq.heapify, i per això és la manera correcta d'arrencar un heap des de dades existents.

Heapsort. Heapify O(n) + extreure el mínim n vegades O(log n) = una llista ordenada en O(n log n) garantit i sense memòria extra (la versió in situ usa un max-heap i va deixant cada màxim al final del mateix array). Aquí queda la menció: els algorismes d'ordenació mereixen el seu propi curs, però ja saps que un dels tres grans (amb mergesort i quicksort) és aquest arbre disfressat d'array.

Max-heap. I si volguessis el màxim primer (tasques per hores estimades, puntuacions)? Opció purista: invertir les comparacions de Monticle (pare ≥ fills). Opció pragmàtica — i l'idiom estàndard amb heapq, que només porta min-heap: negar la clau en inserir (inserir(-valor)) i negar en extreure. El mínim dels negats és el màxim dels originals. Aquest truc reapareixerà a l'exercici top-k de la propera lliçó.

Errors Comuns i Consells

Enfonsar intercanviant amb el fill equivocat. Sempre amb el menor dels dos fills; amb l'altre, la propietat es trenca en el mateix intercanvi. És el bug número u dels heaps casolans.
Oblidar que el heap no està ordenat. m.dades no és una llista ordenada, i recórrer-la no dona ordre ascendent (mira [1, 3, 2, 5, 9, 8]). L'ordre només emergeix extraient. Si necessites llistar-ho tot en ordre repetidament sense buidar res, la teva estructura és l'AVL, no el heap.
Cercar o esborrar un element arbitrari en O(log n). El heap no indexa per valor: localitzar "la tasca T-13" és O(n). Les variants amb mapa auxiliar (posició de cada element) existeixen — així fan els planificadors reals el decrease-key — però no surten gratis ni venen amb heapq.
Ficar-hi dicts (o qualsevol no comparable) a pèl. inserir(tasca) amb dues tasques d'igual prioritat acaba comparant diccionaris: TypeError. La tupla (prioritat, comptador, tasca) és el vestit reglamentari; el comptador, la seva cremallera.
Consell: en producció usa heapq — és C compilat, està ben provat i ara saps exactament què fa per dins (i per què opera sobre una llista normal a la vista). El Monticle propi és per aprendre i per a entrevistes, on "implementa un heap" continua sent un clàssic.

Exercicis

Exercici 1: la traça sense ordinador

Sense executar codi: parteix del heap [2, 5, 3, 9, 6, 8] i aplica (a) inserir(1) i després (b) extreure_minim(). Escriu l'array després de cada intercanvi. Comprova-ho després amb la classe Monticle.

Exercici 2: és un heap vàlid?

Escriu es_min_heap(llista) que verifiqui en O(n) si una llista compleix la propietat de min-heap, i usa-la com a auditor: genera 100 llistes aleatòries, converteix-les en heap inserint element a element en un Monticle, i comprova que les 100 passen l'auditoria (i que la llista original gairebé mai no la passa).

Exercici 3: fusionar safates

Dos equips de TaskFlow fusionen les seves safates d'urgències (dos Monticle amb m i n elements). Escriu fusionar(m1, m2) que retorni un Monticle nou amb tot. Compara el cost de (a) extreure-ho tot de totes dues i inserir-ho al nou, davant de (b) concatenar els arrays interns i "heapificar" enfonsant els interns de darrere cap endavant. Implementa la (b).

Solucions

Solució 1

(a) inserir(1): l'1 entra a i=6 → [2, 5, 3, 9, 6, 8, 1]. El seu pare és i=2 (val 3): 1 < 3 → [2, 5, 1, 9, 6, 8, 3]. Nou pare i=0 (val 2): 1 < 2 → [1, 5, 2, 9, 6, 8, 3]. Fi: dos intercanvis, l'1 al cim.

(b) extreure_minim(): surt l'1; l'últim (3) puja → [3, 5, 2, 9, 6, 8]. Fills del 3: 5 i 2, el menor és el 2: 3 > 2 → [2, 5, 3, 9, 6, 8]. Fills del 3 (i=2): només el 8 (i=5): 3 < 8, fi. Comentari: hem tornat exactament al heap de partida — inserir i extreure el mínim acabat d'inserir deixa la resta com estava, senyal que totes dues operacions toquen només el camí imprescindible.

Solució 2

import random

def es_min_heap(llista):
    for i in range(1, len(llista)):
        if llista[i] < llista[(i - 1) // 2]:   # menor que el seu pare? violació
            return False
    return True

errades = 0
for _ in range(100):
    original = [random.randint(0, 999) for _ in range(50)]
    m = Monticle()
    for x in original:
        m.inserir(x)
    assert es_min_heap(m.dades)                # les 100 passen
    errades += not es_min_heap(original)
print(f"originals que no eren heap: {errades}/100")   # ~100

Comentari: l'auditor recorre cada node comprovant-lo contra el seu pare — n'hi ha prou, perquè la propietat de heap és local (pare-fill directe). Contrasta amb l'ABC, on comprovar només contra el pare era l'error clàssic: allà la propietat parla de subarbres sencers. Mateix gest, validesa oposada — entendre per què és entendre la diferència entre ordre parcial i total. (Un heap de 50 valors aleatoris "de naixement" és raríssim: d'aquí el ~100.)

Solució 3

def fusionar(m1, m2):
    resultat = Monticle()
    resultat.dades = m1.dades + m2.dades           # concatenar: la forma ja és vàlida
    for i in range(len(resultat.dades) // 2 - 1, -1, -1):
        resultat._enfonsar(i)                      # heapify: interns de darrere endavant
    return resultat

a, b = Monticle(), Monticle()
for x in [4, 9, 6]: a.inserir(x)
for x in [1, 7, 3]: b.inserir(x)
c = fusionar(a, b)
print([c.extreure_minim() for _ in range(len(c))])   # [1, 3, 4, 6, 7, 9]

Comentari: l'opció (a) — extreure-ho i inserir-ho tot — costa O((m+n)·log(m+n)); la (b) concatena en O(m+n) i heapifica en O(m+n): lineal total, gràcies a l'argument de la secció bonus (les fulles, més de la meitat, no treballen). El bucle arrenca a l'últim node intern (n//2 - 1, el pare de l'últim element) i retrocedeix fins a l'arrel: quan _enfonsar(i) s'executa, els subarbres d'i ja són heaps vàlids — el mateix raonament "de fills a pares" del postordre. És literalment heapq.heapify escrit a mà.

Conclusió

Promesa complerta: la caixa negra del mòdul 4 està oberta i a dins hi havia un arbre binari complet vivint en un array — la llavor de 06-02 feta estructura. Ja saps el seu contracte (pare ≤ fills: ordre parcial, el just per tenir el mínim a l'arrel, davant de l'ordre total de l'ABC), els seus dos gestos (flotar en inserir, enfonsar en extreure, tots dos O(log n) per un camí arrel-fulla d'altura garantida), la seva arrencada en fred (heapify O(n)), els seus parents (heapsort, max-heap per negació) i el seu lloc a TaskFlow: la SafataUrgencies definitiva, que tanca la taula de cues de prioritat guanyant en l'operació que les altres dues pagaven a O(n). Amb això, l'arsenal del mòdul és complet: arbre genèric per a jerarquies, recorreguts per explotar-les, ABC/AVL per a ordre i intervals, arbre B per al disc i heap per a urgències. La propera lliçó no afegeix teoria: és el gimnàs — sis exercicis progressius on totes aquestes peces treballen juntes sobre TaskFlow, inclosos els clàssics d'entrevista (validar un ABC, reconstruir un arbre, top-k amb monticle). A entrenar.

Monticles (Heaps)

Contingut

La propietat de monticle: ordre parcial, no total

La forma: arbre complet = array sense forats

Inserir: flotar (sift-up)

Extreure el mínim: enfonsar (sift-down)

La classe `Monticle` completa

`SafataUrgencies` 2.0: la caixa negra, oberta

Bonus: heapify en O(n), heapsort i el max-heap

Errors Comuns i Consells

Exercicis

Exercici 1: la traça sense ordinador

Exercici 2: és un heap vàlid?

Exercici 3: fusionar safates

Solucions

Solució 1

Solució 2

Solució 3

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

Monticles (Heaps)

Contingut

La propietat de monticle: ordre parcial, no total

La forma: arbre complet = array sense forats

Inserir: flotar (sift-up)

Extreure el mínim: enfonsar (sift-down)

La classe Monticle completa

SafataUrgencies 2.0: la caixa negra, oberta

Bonus: heapify en O(n), heapsort i el max-heap

Errors Comuns i Consells

Exercicis

Exercici 1: la traça sense ordinador

Exercici 2: és un heap vàlid?

Exercici 3: fusionar safates

Solucions

Solució 1

Solució 2

Solució 3

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

La classe `Monticle` completa

`SafataUrgencies` 2.0: la caixa negra, oberta