Tempo complessità per ottenere numero minimo di elementi di max-heap

Question

mi è stato chiesto in un'intervista:

Qual è la migliore complessità temporale per ottenere l'elemento min (s) da un max-heap?

risposi come O (1) assuma la dimensione heap è nota e il mucchio è implementato come un mucchio binario utilizzando un array. In questo modo, come da mia supposizione, il valore minimo è heap_array[heap_size].

La mia domanda è che se questa risposta è corretta. In caso contrario, qual è la risposta corretta?

Answer 1

La mia domanda è che se questa risposta è corretta.

No, non è corretto. L'unica garanzia che hai, è che ogni nodo contiene l'elemento massimo della sottostruttura sottostante. In altre parole, l'elemento minimo può essere qualsiasi foglia nell'albero.

Se non qual è la risposta corretta?

La risposta corretta è O (n). In ogni fase è necessario attraversare entrambi i sottoalberi sinistro e destro per cercare l'elemento minimo. In effetti, questo significa che devi attraversare tutti gli elementi per trovare il minimo.

Answer 2

La complessità migliore è O(n). Prova bozza:

• L'elemento minimo potrebbe essere in assoluto uno qualsiasi dei nodi di livello più basso (infatti potrebbe anche non essere al livello più basso, ma iniziamo da questi).
• Ci possono essere fino a n/2 nodi di livello più basso.
• Tutti devono essere esaminati, perché quello che stai cercando potrebbe essere nell'ultimo posto in cui si guarda. Esaminando tutto-ma-1 di loro non ti dice se l'ultimo è il minimo o no.
• Quindi sono richiesti gli esami Omega(n).

Il limite è stretto, poiché chiaramente possiamo farlo in O(n) ignorando il fatto che il nostro array sembra essere un heap.

Morale: è probabilmente chiamato un cumulo perché (come con il mucchio di vestiti sul pavimento della camera da letto) è facile arrivare in cima e difficile da ottenere il resto.

Answer 3

elemento min da Max mucchio:

1. ricerca in ultimo livello = O (n/2) = O (n)

2. sostituire l'elemento cercato con l'ultimo elemento e diminuire dimensione heap da 1 = O (1)

3. Applicare Maxheapify sull'elemento sostituito = O (log n)

Tempo Totale = O (n) + O (1) + O (log n) = O (n)

Answer 4

MINIMUM_ELEMENT -> ci vorrà O (n) nel caso di Max mucchio e O (1) in caso di heap min. MAXIMUM_ELEMENT -> richiederà O (1) tempo in caso di heap massimo e O (n) in caso di heap minimo.