Heap (estructura de dades)

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.^[1]

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.^[2]

Una implementació comuna d'un munt és el munt binari, en el qual l'arbre és un arbre binari ^[3] 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. ^[4]

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.^[5]

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.^[6]