Heap (estructura de dades)

Exemple d'un munt màxim binari amb claus de nodes enters entre 1 i 100

En informàtica, un munt (en aglès heap) és una estructura de dades basada en un arbre que compleix la propietat del munt: en un munt màxim, per a qualsevol node C donat, si P és un node pare de C, aleshores la clau (el valor ) de P és més gran o igual a la clau de C. En un munt min, la clau de P és menor o igual que la clau de C. El node a la part "superior" de la pila (sense pares) s'anomena node arrel.

El munt és una implementació màxima eficaç d'un tipus de dades abstracte anomenat cua de prioritat i, de fet, les cues de prioritat sovint s'anomenen "munts", independentment de com es puguin implementar. En un munt, l'element de prioritat més alta (o més baixa) sempre s'emmagatzema a l'arrel. Tanmateix, un munt no és una estructura ordenada; es pot considerar que està parcialment ordenat. Un munt és una estructura de dades útil quan cal eliminar repetidament l'objecte amb la prioritat més alta (o més baixa), o quan les insercions s'han d'intercalar amb eliminacions del node arrel.

Una implementació comuna d'un munt és el munt binari, en el qual l'arbre és un arbre binari complet (vegeu la figura). L'estructura de dades heap, concretament l'heap binari, va ser introduïda per JWJ Williams el 1964, com una estructura de dades per a l'algorisme d'ordenació heapsort. Els munts també són crucials en diversos algorismes de gràfics eficients com l'algoritme de Dijkstra. Quan un munt és un arbre binari complet, té la menor alçada possible: un munt amb N nodes i una branca per a cada node sempre té una alçada de registre N.

Tingueu en compte que, tal com es mostra al gràfic, no hi ha cap ordre implícit entre germans o cosins i cap seqüència implícita per a un recorregut en ordre (com hi hauria, per exemple, en un arbre de cerca binari). La relació de pila esmentada anteriorment s'aplica només entre els nodes i els seus pares, avis. El nombre màxim de fills que pot tenir cada node depèn del tipus de pila.

Els munts es construeixen normalment al lloc en la mateixa matriu on s'emmagatzemen els elements, amb la seva estructura implícita en el patró d'accés de les operacions. Els munts es diferencien d'aquesta manera d'altres estructures de dades amb límits teòrics similars o en alguns casos millors, com ara els arbres Radix, ja que no requereixen memòria addicional més enllà de la que s'utilitza per emmagatzemar les claus.

Operacions

Les operacions habituals que impliquen munts són:

Bàsica

find-max (o find-min): trobar un ítem màxim d'un munt màxim o un element mínim d'un munt mínim, respectivament (també conegut com peek)

inserir: afegint una nova clau al munt (també conegut com, prémer)

extract-max (o extract-min): retorna el node de valor màxim d'un munt màxim [o valor mínim d'un munt mínim] després d'eliminar-lo del munt (també conegut com pop)

delete-max (o delete-min): eliminació del node arrel d'un munt màxim (o munt mínim), respectivament

substituir: desplega l'arrel i prem una tecla nova. Això és més eficient que un pop seguit d'una empenta, ja que només necessita equilibrar-se una vegada, no dues vegades, i és adequat per a munts de mida fixa.

Creació

create-heap: crea un munt buit

heapify: crea un munt a partir d'una matriu d'elements donada

merge (unió): unir dos munts per formar un munt nou vàlid que conté tots els elements d'ambdós, conservant els munts originals.

fusionar: unir dos munts per formar un munt nou vàlid que conté tots els elements de tots dos, destruint els munts originals.

Inspecció

• mida: retorna el nombre d'elements a la pila.
• is-empty: retorna true si el munt està buit, false en cas contrari.

Interna

• clau d'augment o clau de disminució: actualització d'una clau dins d'un munt màxim o mínim, respectivament
• suprimir: suprimir un node arbitrari (seguit de moure l'últim node i tamisar per mantenir la pila)
• tamisar: mou un node cap amunt a l'arbre, sempre que sigui necessari; s'utilitza per restaurar la condició de pila després de la inserció. Es diu "tamís" perquè el node es mou per l'arbre fins que arriba al nivell correcte, com en un sedàs.
• tamisar: mou un node cap avall a l'arbre, de manera semblant a tamisar cap amunt; s'utilitza per restaurar la condició de pila després de la supressió o la substitució.

Implementació

Exemple d'un munt màxim binari complet amb claus de nodes enters d'1 a 100 i com s'emmagatzemaria en una matriu.

Els munts solen implementar-se amb una matriu, de la següent manera:

• Cada element de la matriu representa un node de la pila, i
• La relació pare/fill es defineix implícitament pels índexs dels elements a la matriu.

Per a un munt binari, a la matriu, el primer índex conté l'element arrel. Els dos índexs següents de la matriu contenen els fills de l'arrel. Els quatre índexs següents contenen els quatre fills dels dos nodes fills de l'arrel, i així successivament. Per tant, donat un node a l'índex i, els seus fills es troben als índexs $2i+1$ i $2i+2$ , i el seu pare es troba a l'índex ⌊(i−1)/2⌋. Aquest senzill esquema d'indexació fa que sigui eficient moure "amunt" o "avall" l'arbre.

L'equilibri d'un munt es realitza mitjançant operacions de tamisar o tamisar (intercanviant elements que estan fora d'ordre). Com que podem construir un munt a partir d'una matriu sense necessitat de memòria addicional (per als nodes, per exemple), l'heapsort es pot utilitzar per ordenar una matriu al seu lloc.

Tot i que diferents tipus d'heaps implementen les operacions de manera diferent, la forma més comuna és la següent:

• Inserció: afegir l'element nou al final de la pila, al primer espai lliure disponible. Si això violarà la propietat del munt, tamisar el nou element (operació de natació ) fins que s'hagi restablert la propietat del munt.
• Extracció: extreure l'arrel i inseriu l'últim element de la pila a l'arrel. Si això infringeix la propietat de l'emmagatzematge dinàmic, cerqueu la nova arrel (operació de sink) per restablir la propietat de l'emmagatzematge dinàmic.
• Substitució: extreure l'arrel i introduir l'element nou a l'arrel i tamiseu. En comparació amb l'extracció seguida de la inserció, això evita un pas de tamís.

La construcció d'un munt binari (o d -ary) a partir d'una matriu d'elements donada es pot realitzar en temps lineal utilitzant l' algorisme de Floyd clàssic, amb el pitjor nombre de comparacions igual a 2N − 2s₂(N) − e₂(N) (per a un munt binari), on s₂(N) és la suma de tots els dígits de la representació binària de N i e₂(N) és l'exponent de 2 en la factorització primera de N. Això és més ràpid que una seqüència d'insercions consecutives en un munt originalment buit, que és log-lineal.