Taula de continguts:
Definició: què significa Heap?
Un heap, en el context de l'estructura de dades, és una estructura de dades basada en l'arbre que satisfà la propietat heap, on a cada element se li assigna un valor clau o una ponderació. La clau de valor inferior sempre té un node pare amb una clau de valor superior. A això s'anomena estructura max-heap, i entre tots els nodes, el node arrel té la clau més alta.
De vegades, una estructura basada en l’arbre té una regla d’estructura invertida, on un element amb una clau de valor superior sempre té una clau de valor inferior com a node pare. A això s’anomena estructura min-heap, i entre tots els nodes, el node arrel té la clau més baixa.
Techopedia explica Heap
No hi ha restriccions pràctiques en el nombre de fills que cada node pot tenir en un munt, malgrat que cada node en tingui dos com a màxim. El heap es considera la implementació més eficient d’un tipus de dades abstractes, coneguda com la cua de prioritats. La implementació de pila és essencial en diversos algoritmes de gràfics (inclòs l'algorisme de Dijkstra) així com en l'algorisme de classificació de l'heapsort.
Els heaps tenen diverses variacions que actuen com a implementacions de cues de prioritat del tipus de dades abstractes amb alta eficiència. Moltes aplicacions, com els algoritmes gràfics, requereixen la implementació de cues de prioritat.
Una matriu és la forma de implementació més comuna d'heap, on no calen indicadors per enllaçar entre els seus elements.
Els munts realitzen diverses operacions, incloent:
- Find-max: cerques del node de la clau més alta entre un grup de nodes
- Find-min: cerques del node de clau més baix entre un grup de nodes
- Delete-max: elimina el node de la clau més alta entre un grup de nodes
- Eliminar-min: elimina el node clau més baix d'un grup de nodes
Els munts també inclouen funcions que realitzen canvis de fusió, inserció i claus.
Aquesta definició es va escriure en el context de l'estructura de dades
