For faster navigation, this Iframe is preloading the Wikiwand page for Monticle binari.

Monticle binari

De Viquipèdia

Els Monticles binaris (binary Heaps en anglès) són un cas particular i senzill de l'estructura de dades Monticle, i està basada 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

Inserció d'un element

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

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

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

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.

Un arbre binari complet guardat com un array
Un arbre binari complet guardat com un array

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

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Monticle binari
{{bottomLinkPreText}} {{bottomLinkText}}
Monticle binari
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.