[ALGORITMI] - Mediano di una matrice

[Adva1]

Salve a tutti, in questi giorni sto sbattendo la testa con un'esercizio d' esame proposto nel corso di Algoritmi e strutture dati.
Il testo recita:

Sia M una matrice k x n di valori distinti. I valori di ognuna delle k righe sono ordinati in modo crescente. Progettare un algoritmo che, presa M, restituisca il valore mediano della matrice, ovvero il valore che, se si considerano in ordine crescente tutti gli elementi della matrice si trova in posizione $ (nk)/2 $ (parte intera inferiore) $+1$. L'algoritmo deve avere complessità temporale $ O(nklnk)$ e deve usare memoria ausiliaria $O(k)$.
Un esempio per capirci meglio:
k=3, n=4
$M = ((1,2,3,8),(10,17,20,30),(5,11,21,23))$
La matrice ordinata:
$M = (1,2,3,5,8,10,11,17,20,21,23,30)$
Il valore mediano si trova in posizione $(3*4)/2+1 = 7$
Quindi il valore mediano è 11.

Purtroppo non riesco ad avere l'intuizione, non voglio la soluzione, vorrei gentilmente uno spunto, mi sta facendo uscire pazzo

[apatriarca]

Suppongo che tu possa fare una specie di "merge" delle righe in cui memorizzi gli elementi più piccoli di ogni riga in un heap.

[Adva1]

Il merge occupa spazio lineare negli elementi da ordinare, quindi in questo caso occuperebbe $O(kn)$ e sono fuori con le specifiche. Non capisco l'heap in cosa può tornarmi utile?

[apatriarca]

Parlando di merging delle righe non mi riferivo alla creazione di un array con tutti gli elementi in ordine. Piuttosto di un modo di visitare gli elementi in ordine. Non li memorizzi insomma, ma ti fermi quando arrivi all'elemento mediano. Più in pratica si tratta di prendere tutti gli elementi della prima colonna e di inserirli (insieme al loro numero di riga) in un min-heap. A questo punto si estrae l'elemento più piccolo dall'heap e si sostituisce con il successivo elemento sulla sua riga. In ogni momento l'heap contiene al massimo \(k\) elementi per cui l'occupazione di memoria è \(O(k)\) come richiesto. Inoltre si visitano circa \(n\,k/2\) elementi e per ogni elemento devi fare una estrazione del numero più piccolo dall'heap e un nuovo inserimento (che nel caso di un binary heap hanno complessità \(O(\log_2(k)\)..).

[Adva1]

Caspita

Ho capito

Apatriarca grazie mille, sei un genio!