Esercizio 14k-esimo elemento più piccolo con uno heap

Idea

Il termine $n$ suggerisce una costruzione bottom-up di uno heap, che costa $\Theta(n)$; il termine $k \log n$ suggerisce $k$ operazioni di removeMin, ciascuna $\Theta(\log n)$. Il minimo estratto per $k$-esimo è il $k$-esimo più piccolo (vedi HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap → e Costruzione di uno heapCostruire uno heap da un array di n entry: approccio top-down con n-1 insert, Theta(n log n); approccio bottom-up con down-heap dalle foglie verso la radice, Theta(n), con dimostrazione della somma; esempi svolti, in loco; unione di due alberi con heap-order.Costruzione di uno heap →). Ordinare tutto l'insieme costerebbe $\Theta(n \log n)$, peggio quando $k$ è piccolo (ad esempio per la mediana si hanno $k=n/2$; per il minimo $k=1$: basta una scansione, $\Theta(n)$). È di fatto un heap sort fermato dopo $k$ passi (Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →).

Algoritmo

Algoritmo kEsimoMinimo(A, n, k)
Input: array A[1..n] di interi distinti, intero 1 <= k <= n
Output: il k-esimo elemento più piccolo di A
P <- A                                    (lavoro in loco sull'array)
for j <- floor(n/2) downto 1 do           (costruzione bottom-up di un min-heap)
    down-heap bubbling a partire da P[j]
last <- n
for t <- 1 to k - 1 do
    P[1] <- P[last]; last <- last - 1     (removeMin, scartando il minimo)
    down-heap bubbling a partire da P[1]
return P[1]                               (il k-esimo minimo: la radice)

L'ultima operazione non serve completarla: dopo $k - 1$ rimozioni la radice dello heap è il $k$-esimo più piccolo (equivalentemente, si può fare removeMin() $k$ volte e restituire l'ultimo valore estratto).

Correttezza. Lo heap contiene sempre gli elementi non ancora scartati. Dopo la costruzione la radice è il minimo (1° più piccolo). A ogni removeMin si toglie il minimo corrente, quindi dopo $t$ rimozioni sono stati tolti i $t$ elementi più piccoli e la radice è il $(t+1)$-esimo. Dopo $k - 1$ rimozioni la radice è il $k$-esimo.

Esempio

$A = [7, 2, 9, 4, 1, 8]$, $k = 3$.

• Bottom-up ($\lfloor 6/2 \rfloor = 3$): $j = 3$: $[7, 2, 8, 4, 1, 9]$; $j = 2$: $[7, 1, 8, 4, 2, 9]$; $j = 1$: $[1, 2, 8, 4, 7, 9]$ (il $7$ scende prima scambiandosi con $1$, poi con $2$).
• Rimozione 1 (si scarta $1$): $9$ in radice, $[9, 2, 8, 4, 7] \to [2, 9, 8, 4, 7] \to [2, 4, 8, 9, 7]$.
• Rimozione 2 (si scarta $2$): $7$ in radice, $[7, 4, 8, 9] \to [4, 7, 8, 9]$.
• La radice è $4$: il terzo più piccolo, in accordo con l'ordinamento $1, 2, 4, 7, 8, 9$.

Complessità

• Costruzione bottom-up: $\Theta(n)$ (somma dei costi per livello, vedi Costruzione di uno heapCostruire uno heap da un array di n entry: approccio top-down con n-1 insert, Theta(n log n); approccio bottom-up con down-heap dalle foglie verso la radice, Theta(n), con dimostrazione della somma; esempi svolti, in loco; unione di due alberi con heap-order.Costruzione di uno heap →).
• $k - 1$ rimozioni: ciascuna $O(\log n)$ (altezza dello heap $\le \lfloor \log_2 n \rfloor$): $O(k \log n)$.

Totale: $O(n + k \log n)$. Per $k = O(n / \log n)$ è lineare (perché allora $k\log n=O(n)$). Per confronto con l'ordinamento ($\approx n\log_2 n$) ecco i numeri per $n=1000$:

Per $k=10$ l'heap fa circa $1000+100=1100$ operazioni contro $\approx 10\,000$ dell'ordinamento. Il punto di incrocio, dove $n+k\log_2 n=n\log_2 n$, è $k=n\,\frac{\log_2n-1}{\log_2 n}\approx 0{,}9\,n$. Se $k$ è vicino a $n$ non conviene rispetto all'ordinamento ($O(n \log n)$ in entrambi i casi), ma la richiesta dell'esercizio è proprio questo limite.

Varianti

Con una coda con priorità su array non ordinato la costruzione è banale ma ogni removeMin costa $\Theta(n)$: $\Theta(kn)$. Con lista ordinata si paga $\Theta(n \log n)$ per ordinare. Lo heap bilancia i costi (vedi Code con prioritàEntry chiave-valore; ADT coda con priorità (insert, min, removeMin) con chiave minima = priorità massima; esempio di esecuzione; applicazioni; implementazioni con lista non ordinata e ordinata e relativi costi; ordinamento tramite coda con priorità.Code con priorità →).

Errori comuni

• Costruire lo heap con $n$ insert (top-down): $\Theta(n \log n)$, che viola il limite richiesto.
• Errore di uno: se si fanno $k$ estrazioni e si restituisce la radice dopo l'ultima, si ottiene il $(k+1)$-esimo; vale o il valore estratto alla $k$-esima estrazione, o la radice dopo $k - 1$ estrazioni.
• Usare un max-heap senza adattare $k$ (con un max-heap si cerca il $k$-esimo più grande).
• Dimenticare che gli elementi sono distinti: con ripetizioni "$k$-esimo più piccolo" va ridefinito.