Heap (struttura dati): differenze tra le versioni

Versione delle 09:19, 24 apr 2018

Versione delle 10:54, 24 apr 2018

Riga 1:

{{nota disambigua|lo spazio di memoria allocato dinamicamente in RAM|Gestione della memoria}}

[[File:Max-Heap.svg|thumb|right|Esempio di un max heap [[Albero binario|binario]] con nodi da 1 a 100]]

In [[informatica]], un '''heap''' (lett. "mucchio") è una [[struttura dati]] basata sugli [[Albero (informatica)|alberi]] che soddisfa la "proprietà di heap": se A è un genitore di B, allora la chiave 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. 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