<aside> ℹ️

Un heap binario è una struttura dati composta da un array che può essere considerato come un albero binario quasi completo

</aside>

• Altezza → $\Theta(log_2n)$
• Dimensione array → length[A]
• Elementi memorizzati → heap-size[A]
• Radice → A[1]
• Padre e figli di un nodo i →
  • Padre → parent[i] = i/2
  • Figlio sinistro → left[i] = 2i
  • Figlio destro → right[i] = 2i + 1

Max-heap & Min-heap

<aside> ℹ️

Max-heap: in un max-heap ogni nodo i diverso dalla radice è tale che:

A[parent[i]] >= A[i]

• L’elemento più grande di un max-heap viene memorizzato nella radice
• Un sottoalbero di un nodo u contiene nodi il cui valore non è mai maggiore del valore del nodo u </aside>

<aside> ℹ️

Min-heap: in un min-heap ogni nodo i diverso dalla radice è tale che:

A[parent[i]] <= A[i]

• L’elemento più piccolo di un min-heap viene memorizzato nella radice
• Un sottoalbero di un nodo u contiene nodi il cui valore non è mai minore del valore del nodo u </aside>

Code di min-priorità | Min-Heap

Operazioni:

• Insert(S,x) → Inserisce x nell’insieme S
• Minimum(S) → restituisce l’elemento di S con chiave minima
• Extract-Min(S) → elimina e restituisce l’elemento di S con chiave minima
• Decrease-Key(S,x,k) → decrementa il valore della chiave di x al nuovo valore k (qui assumiamo k <= dell’attuale valore della chiave di x)

Coda di max-priorità | Max-Heap

Operazioni:

• Insert(S,x) → Inserisce x nell’insieme S
• Maximum(S) → restituisce l’elemento di S con chiave più grande