[Algoritmi] trovare massimo in min-heap

[tvd_40]

Salve a tutti!

Mi trovo di fronte a questo esercizio che riesco a risolvere solo in parte.

Si assuma che n numeri diversi fra loro siano memorizzati in un min-heap.
Si dia un algoritmo che in tempo O(1) trovi il terzo elemento più piccolo di A.
Sotto l'ipotesi che i sia costante, si dica come l'i-esimo elemento più grande di A possa essere trovato in tempo O(1).

Per quanto riguarda il terzo minimo: confronto A[2] e A[3] e trovo il secondo minimo. Il terzo sarà o l'escluso dal primo confronto oppure il figlio destro o figlio sinistro del secondo minimo. Giusto?
Ho preso in considerazione la proprietà dei min-heap secondo cui ogni nodo memorizza un valore che è maggiore di quello del padre.

Per quanto riguarda il massimo invece non riesco proprio a venirne a capo
Di sicuro sarà nelle foglie ma come faccio a trovarlo in tempo O(1)??

Grazie a chi vorrà dedicarmi un minuto
sarei felicissima di capirci qualcosa in più!

[Giova411]

"tvd_40":
Per quanto riguarda il massimo invece non riesco proprio a venirne a capo
Di sicuro sarà nelle foglie ma come faccio a trovarlo in tempo O(1)??

Penso che bisogna seguire il figlio DX fino a trovare un nodo che non sia più figlio DX
(forse però sto confondendo coi più "semplici" ABR).
Forse si potrebbe "hepifizzare" la struttura con un MaxHeap ma non costa certo solo O(1)
Tu, se devi buttarla lì, che ragionamento faresti?
Accedi in modo diretto pensando ad un'implementazione con un vettore dei padri partendo dall'indice 1?