Monticle binari
Els Monticles binaris (Binary Heaps en anglès) són un cas particular i senzill de l'estructura de dades Monticle, i estan basats en un arbre binari balancejat, que es pot veure com un arbre binari amb dues restriccions addicionals:
- Propietat de monticle
- Cada node conté un valor superior al dels seus fills (per a un monticle per màxims) o més petit que el dels seus fills (per a un monticle per mínims).
- Arbre semicomplet
- L'arbre està balancejat i en un mateix nivell les insercions es realitzen d'esquerra a dreta.
Els monticles per màxims s'utilitzen freqüentment per representar cues de prioritat. A continuació es mostren dos monticles un per mínims i altre per màxims que representen el mateixes valors.
1 11 / \ / \ 2 3 9 10 / \ / \ / \ / \ 4 5 6 7 5 6 7 8 / \ / \ / \ / \ 8 9 10 11 1 2 3 4
L'ordre dels nodes germans en un monticle no està especificat en la propietat de monticle , de manera que els subarbre d'un node són intercanviables.
Operacions sobre monticles
[modifica]Inserció d'un element
[modifica]La inserció d'un element es realitza afegint l'element en la posició que respecta la restricció d'arbre semicomplet però possiblement invalidant la propietat de monticle , per a després remuntar cap a l'arrel restaurant la propietat de monticle per intercanvi del valor de la posició desordenada pel valor del seu pare. Aquesta reorganització es realitza en temps O (log n ).
Exemple
[modifica]Al següent monticle per màxims la posició on es pot inserir està marcada amb una lletra X.
11 / \ 5 8 / \ / 3 4 X
Per inserir el valor 15 en aquest monticle, s'insereix el valor en la posició marcada amb la qual cosa invalida la propietat de monticle, ja que 15 és major que 8. Per restaurar la propietat de monticle s'intercanvia primer el 15 amb el 8, obtenint el següent arbre:
11 / \ 5 15 / \ / 3 4 8
No obstant això, la propietat de monticle encara no es compleix, ja que 15 és major que 11, de manera que cal fer un nou intercanvi:
15 / \ 5 11 / \ / 3 4 8
El resultat si és un monticle per màxims.
Eliminació de l'element màxim
[modifica]Per esborrar l'element màxim del monticle, de la manera més eficient es pot prendre l'element de la posició que ha de quedar buida, posant-lo en l'arrel (així complint la propietat d'arbre), i després intercanviar aquest valor amb el màxim dels seus fills fins a satisfer la propietat de monticle (si és de màxims), o intercanviar amb el mínim dels seus fills (si és de mínims). Aquesta reorganització es pot realitzar també en temps O (log n ). Partint del mateix monticle que abans:
11 / \ 5 8 / \ 3 4
En eliminar l'11, aquest es reemplaça per 4 (el valor del node que s'ha d'eliminar):
4 / \ 5 8 / 3
En aquest arbre no es compleix la propietat de monticle atès que 8 és major que 4. En intercanviar aquests dos valors s'obté un monticle:
8 / \ 5 4 / 3
Representació de monticles
[modifica]Si bé es pot utilitzar un arbre binari per representar un monticle, la condició d'arbre permet representar fàcilment un monticle en un vector posant els elements per nivells i en cada nivell, els elements d'esquerra a dreta.
Atès que l'arbre és complet, no cal emmagatzemar apuntadors a l'arbre. Sempre es pot calcular la posició dels fills o la del pare a partir de la posició d'un node en l'arranjament (comptant les posicions de l'arranjament a partir de zero):
- El node arrel s'emmagatzema en la posició 0 de la reparació.
- Els fills d'un node emmagatzemat en la posició k s'emmagatzemen en les posicions 2k +1 i 2k +2 respectivament.
Es dedueix que el pare d'un node que està en la posició k ( k> 0 ) està emmagatzemat en la posició ((k-1) div 2) .
Enllaços externs
[modifica]