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.

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. 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.