Heap

Un albero binario è detto heap se è completo fino al livello $h-1$, e il resto delle foglie sono verso sinistra.

Per esempio, un albero può essere:

e potrà essere rappresentato in un array come A = [16, 3, 10, 0, 2, 4].

Per cui il padre di i si raggiunge con floor(i/2), mentre il figlio sinistro con 2*i e il destro con 2*i+1.

In base all'ordinamento di ogni nodo i, un heap può essere specializzato in:

• Max heap, se A[parent(i)] >= A[i]
• Min heap, se A[parent(i)] <= A[i]

che garantiscono che la radice contiene il nodo più grande o più piccolo rispettivamente.

Proprietà

Per un heap di $n$, si ha che:

1. Ha altezza $h=\lfloor \log n\rfloor$.

   Questo si può dimostrare perchè: $$\left(\sum _{i=0}^{n-1}{2}^i\right)+1\le n\le \sum _{i=0}^h{2}^i$$ cioè che $n$ è tra il numero di nodi di un albero completo alto $h-1$ e $h$, per cui: $$\begin{array}{rl}\frac{2^h-1}{2-1}+1\le n\le \frac{2^{h+1}-1}{2-1}& \iff 2^h\le n\le 2^{h+1}-1<2^{h+1}\\ & \iff h\le \log n<h+1\end{array}$$ e quindi $h=\lfloor \log n\rfloor$ dato che $h\in \mathbb{N}$.

2. Le foglie occupano le posizioni $\lfloor \frac{n}{2}\rfloor +1,\lfloor \frac{n}{2}\rfloor +2,...,n$.

3. Può possedere al più $\lceil \frac{n}{2^{h+1}}\rceil$ nodi che hanno altezza $h$.

   Infatti con $h=0$ ci sono $\lceil \frac{n}{2}\rceil$ foglie, mentre con $h=\lfloor \log n\rfloor$ ci sono $\lceil \frac{n}{2n}\rceil =\lceil \frac{1}{2}\rceil =1$ nodi.

Implementazione

• Heapify, per ripristinare l'heap sapendo che left(i) e right(i) sono max heap

  max_heapify(Heap A, Node i)
    l = left(i)
    r = right(i)
    max = i
    if l <= A.heap_size and A[l] > A[i]
      max = l
    if r <= A.heap_size and A[r] > max
      max = r
    if i != max
      swap(A[i], A[max])
      max_heapify(A, max)
  

  dove A.heap_size corrisponde a $n$ mentre $T(n)=O(h)$ cioè $O(\log n)$ per la prima proprietà.

• Costruzione, per generare gradualmente l'heap da $\lfloor \frac{n}{2}\rfloor$, cioè i nodi sopra le foglie, fino alla radice

  build_max_heap(Array A)
    A.heap_size = A.length
    for i = floor(A.length/2) down to 1
      max_heapify(A, i)
  

  che è corretto per l'invariante del for:

  Ogni nodo in A[i+1..n] è radice di un rispettivo max heap

  che al termine i = 0 quindi A[1..n] sono radici di max heap, compreso A[1] che è la radice.

  Ha complessità $T(n)=O(n\log n)$, ma più precisamente: $$T(n)\le \left(\sum _{h=0}^{\lfloor \log n\rfloor }\lceil \frac{n}{2^{h+1}}\rceil \right)O(h)=O\left(n\sum _{h=0}^{\lfloor \log n\rfloor }\frac{h}{2^h}\right)=O\left(n\sum _{h=0}^{\infty }\frac{h}{2^h}\right)=O(2n)=O(n)$$ perchè $n\le \sum _{h=0}^{\lfloor \log n\rfloor }\lceil \frac{n}{2^{h+1}}\rceil$ per la prima e terza proprietà e $\sum _{i=0}^{\infty }i{x}^i=\frac{x}{(1-x{)}^2}$ se $|x|<1$.