Metraipolis › archive › dc_5007b4df8218

Heap (struttura dati) — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Heap_(struttura_dati)
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T17:57:26.249Z
SHA-256 of the archived text
87fe3d59195517d02e16f14ee363a86a660d06185e457ccc2a953bc77d8e7885
Stable URL of this page
https://metraipolis.com/documento/dc_5007b4df8218

How to cite

Heap (struttura dati) — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Heap_(struttura_dati) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_5007b4df8218 (Metraipolis archive dc_5007b4df8218, sha256 87fe3d59195517d02e16f14ee363a86a660d06185e457ccc2a953bc77d8e7885)
BibTeX
@misc{dc5007b4df8218,
  title = {Heap (struttura dati) — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Heap_(struttura_dati)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_5007b4df8218; sha256 87fe3d59195517d02e16f14ee363a86a660d06185e457ccc2a953bc77d8e7885},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Heap_(struttura_dati). Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In informatica, un heap (lett. "mucchio") è una struttura dati basata sugli alberi che soddisfa la "proprietà di heap": se A è un genitore di B, allora la chiave (il valore) di A è ordinata rispetto alla chiave di B conformemente alla relazione d'ordine applicata all'intero heap. Di conseguenza, gli heap possono essere suddivisi in "max heap" e "min heap". In un max heap, le chiavi di ciascun nodo sono sempre maggiori o uguali di quelle dei figli, e la chiave dal valore massimo appartiene alla radice (detta anche nodo root). In un min heap, le chiavi di ciascun nodo sono sempre minori o uguali di quelle dei figli, e la chiave dal valore minimo appartiene alla radice. Quindi, dato un heap v ed un indice di posizione j, v si dice min-heap: se v [ P a d r e ( j ) ] < v [ j ] , ∀ j {\displaystyle v[Padre(j)]<v[j],\forall j} max-heap: se v [ P a d r e ( j ) ] > v [ j ] , ∀ j {\displaystyle v[Padre(j)]>v[j],\forall j} In particolare, da un punto di vista di array, descriviamo gli indici assunti da heap per i vari nodi: padre = i / 2 {\displaystyle i/2} nodo sinistro (left): 2 i {\displaystyle 2i} nodo destro (right) 2 i + 1 {\displaystyle 2i+1} In questo modo si garantisce che compiendo un qualsiasi percorso che parte da un nodo dell'albero e scendendo nella struttura verso le foglie, si attraversano nodi con chiave sempre maggiore dell'ultima foglia visitata. La scelta di utilizzare un tipo di heap anziché l'altro è data dal tipo di impiego che se ne vuole fare. Da notare che, come si vede nel grafo a fianco, non è implicato alcun ordine specifico tra nodi fratelli o cugini, ovvero, i nodi non sono ordinati trasversalmente (come invece accade, ad esempio, nell'albero binario di ricerca). Gli heap sono essenziali negli algoritmi della teoria dei grafi (come l'algoritmo di Dijkstra) o negli algoritmi di ordinamento come l'heapsort. Un'implementazione molto comune di un heap è l'heap binario, basato su un albero binario completo (come quello in figura). L'heap è, inoltre, una delle implementazioni più efficienti di un tipo di dato astratto chiamato coda di priorità. Essi vengono inoltre utilizzati negli algoritmi di selezione o il merge per l'elemento k-esimo, prendendo gli stream di input e convertendoli ordinatamente in stream di output.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «Heap (struttura dati)» — https://it.wikipedia.org/wiki/Heap_(struttura_dati)
Wikidata Q274089 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q274089
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Heap_(struttura_dati)?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 150616947, consultata il 2026-10-15T17:09:23.598Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 6c910c34fee348631014cc1c79e4bf028d72a5275e1889ccc6b343b42ff7c003