Stampa i maggiori elementi K in un determinato heap in O (K * log (K))?

Dato il seguente problema, non sono completamente sicuro della mia attuale soluzione:

Domanda:

Dato un heap massimo con n elementi, che è memorizzato in una matrice A , è ansible stampare tutti i maggiori elementi K in O(K*log(K)) ?

La mia risposta :

Sì, poiché cercare un elemento richiede O(log(K)) , quindi farlo

per gli elementi K occorrerebbe tempo di esecuzione O(K * log(K)) .

Questo è ansible in un heap massimo perché si stanno stampando solo gli elementi dall’albero, non estraendoli.

Inizia identificando l’elemento massimo, che si trova nel nodo radice. Forma un puntatore a un nodo e aggiungilo a un elenco “massimo” vuoto. Quindi, per ciascuno dei valori k , eseguire i seguenti passaggi in un ciclo.

  • Apri l’elemento massimo dall’elenco, prendendo O (1).
  • Stampa il suo valore, prendendo O (1).
  • Inserisci ognuno dei bambini di questo elemento massimo nell’elenco. Mantieni ordinamento quando li inserisci, prendendo O (log (dimensione della lista)). La dimensione massima di questo elenco, dal momento che stiamo eseguendo questo ciclo k volte, è di dimensioni branch * k. Pertanto questo passo richiede O (log (k)).

In totale, quindi, il tempo di esecuzione è O (klog (k)), come desiderato.

La ricerca di un elemento in un heap di dimensioni N non è O (K). Innanzitutto, non ha senso che la complessità temporale per la ricerca di un elemento dipenda dal numero di elementi che stai cercando di estrarre (che è ciò che rappresenta K). Inoltre, non esiste una ricerca in un heap, a meno che non si contenga la ricerca standard di look-at-ogni-element in O (N).

Tuttavia, la ricerca dell’elemento più grande in un heap è O (1) in base alla progettazione (ovviamente sto assumendo che si tratti di un max-heap, quindi l’elemento massimo è in cima all’heap) e rimuove l’elemento più grande da un heap di la dimensione N è O (log (N)) (sostituiscilo con un elemento foglia e fai ricadere quella foglia nel mucchio).

Quindi, estrarre elementi K da un heap e restituire l’heap di elementi non estratti , richiederebbe il tempo O (K · log (N)).

Cosa succede se estrai elementi K non distruttivi dall’heap? È ansible farlo mantenendo un heap-of-heap (dove il valore di un heap è il valore del suo elemento massimo). Inizialmente, questo heap-of-heap contiene solo un elemento (l’heap originale). Per estrarre il prossimo elemento massimo, si estrae l’heap in alto, si estrae l’elemento superiore (che è il massimo) e quindi si reinseriscono i due sotto-heap nell’heap-of-heaps.

Questo aumenta l’heap di heap di uno su ogni rimozione (rimuovi uno, aggiungi due), il che significa che non terrà mai più di elementi K , e quindi il remove-one-add-two richiederà O (log (K) ). Iterate questo e otterrete un algoritmo O (K · log (K)) effettivo che restituisce i primi elementi K, ma non è in grado di restituire l’heap di elementi non estratti.

Ho trovato le altre risposte confuse, quindi ho deciso di spiegarlo con un vero esempio di heap. Si supponga che l’heap originale sia la dimensione N e si desideri trovare i k più grandi elementi, Questa soluzione richiede O (klogk) e O (k) di spazio.

  10 / \ 5 3 / \ /\ 4 1 2 0 Original Heap, N = 7 

Vuoi trovare il 5 ° elemento più grande. k = 5 Nota: nel nuovo heap, è necessario memorizzare il puntatore nell’heap originale. Ciò significa che non si rimuove o non si modifica l’heap originale. L’heap originale è di sola lettura. Pertanto, non è mai necessario eseguire operazioni che richiedono il tempo O (logN).

Sia x ‘il puntatore al valore x nell’heap originale.

1a Iterazione: Ottieni il puntatore del nodo radice nel nuovo heap

Passaggio 1: aggiungi il puntatore al nodo 10

  10' New Heap, size = 1, root = 10', root->left = 5, root right->3 

Stampa il 1 ° elemento più grande = 10

Seconda iterazione: fai riferimento all’heap originale e inserisci entrambi i suoi figli nel nuovo heap. (Memorizzando i puntatori a loro e non il valore stesso). Il motivo per cui si desidera memorizzare il puntatore è che è ansible accedervi in ​​O (1) dall’heap originale in un secondo momento per cercare i propri figli anziché O (N) per cercare dove si trova quel valore nell’heap originale.

Passaggio 2a: cercare il figlio sinistro del nodo principale del nuovo heap dall’heap originale. Aggiungi un puntatore per il figlio sinistro (in questo caso, 5 ‘) al nuovo heap.

  10' / 5' New Heap, size = 2, root = 10', root->left = 5, root right->3 

Passaggio 2b: cercare il figlio destro del nodo root del nuovo heap dall’heap originale. Aggiungi un puntatore per il figlio sinistro (in questo caso, 3 ‘) al nuovo heap.

  10' / \ 5' 3' New Heap, size = 3, root = 10', root->left = 5, root right->3 

Passaggio 2c: rimuovere il nodo root da New Heap. (Scambia il nodo massimo con la parte destra più a destra, rimuovi il nodo radice e svuota la root corrente per mantenere la proprietà heap)

  10' swap 3' remove & bubble 5' / \ => / \ => / 5' 3' 5' 10' 3' New Heap, size = 2, root = 5', root->left = 4, root right->1 

Stampa il 2 ° elemento più grande = 5

Passaggio 3a: cercare figlio sinistro del nodo radice del nuovo heap dall’heap originale. Aggiungi un puntatore per il figlio sinistro (in questo caso, 4 ‘) al nuovo heap.

  5' / \ 3' 4' New Heap, size = 3, root = 5', root->left = 4, root right->1 

Passaggio 3b: cercare il figlio destro del nodo principale del nuovo heap dall’heap originale. Aggiungi un puntatore per il figlio sinistro (in questo caso, 1 ‘) al nuovo heap.

  5' / \ 3' 4' / 1' New Heap, size = 4, root = 5', root->left = 4, root right->1 

Passaggio 3c: rimuovere il nodo root da New Heap. (Scambia il nodo massimo (5 ‘) di New Heap con la parte più a destra dell’heap originale (1’) dal New Heap, rimuovi il nodo root e svuota la root corrente per mantenere la proprietà heap)

  5' Swap 1' remove & bubble 4' / \ => / \ => / \ 3' 4' 3' 4' 3' 1' / / 1' 5' New Heap, size = 3, root = 4', root->left = NULL, root right->NULL 

Stampa il terzo elemento più grande = 4

Il passo 4a e il passo 4b non fanno nulla poiché il nodo radice non ha figli in questo caso dall’heap originale.

Passaggio 4c: rimuovere il nodo root da New Heap. (Scambia il nodo massimo con la maggior parte a destra, rimuovi il nodo root e svuota la root corrente per mantenere la proprietà heap in New Heap)

  4' Swap 1' remove & bubble 3' / \ => / \ => / 3' 1' 3' 4' 1' New Heap, size = 2, root = 3', root->left = 2, root right->0 

Stampa il quarto elemento più grande = 3

Passaggio 5a: cercare il figlio sinistro del nodo principale del nuovo heap dall’heap originale. Aggiungi un puntatore per il figlio sinistro (in questo caso, 2 ‘) al nuovo heap.

  3' / \ 1' 2' New Heap, size = 3, root = 3', root->left = 2, root right->0 

Passaggio 5b: cercare il figlio destro del nodo principale del nuovo heap dall’heap originale. Aggiungi un puntatore per il figlio sinistro (in questo caso, 0 ‘) al nuovo heap.

  3' / \ 1' 2' / 0' New Heap, size = 4, root = 3', root->left = 2, root right->0 

Passaggio 5c: rimuovere il nodo root da New Heap. (Scambia il nodo massimo (3 ‘) con la parte più a destra dell’heap originale (che è 0’) nel Nuovo heap, rimuovi il nodo radice e svuota la root corrente per mantenere la proprietà heap in Nuovo heap)

  3' Swap 0' Remove & Bubble 2' / \ => / \ => / \ 1' 2' 1' 2' 1' 0' / / 0' 3' New Heap, size = 3, root = 2', root->left = NULL, root->right = NULL 

Stampa il quinto elemento più grande = 2

Infine, dato che abbiamo eseguito k iterazioni, k = 5. Ora possiamo estrarre il valore dell’elemento radice dal nuovo heap. In questo caso, il valore è 2. Pertanto, abbiamo trovato il k più grande valore dall’heap originale.

Complessità temporale, T (N, k) = O (klogk) Complessità spaziale, S (N, k) = O (k)

Spero che questo ti aiuti!

Presto Chee Loong,

Università di Toronto.

Infatti, è troppo facile, l’estrazione dell’elemento massimo è O(log(N)) dove N è la dimensione dell’heap. e N≠K

Aggiungerò che la ricerca di un elemento casuale è O(N) e non O(Log(N)) , ma in questo caso vogliamo estrarre il massimo.

 It is a simple and elegant algorithm to get first k elements of a max heap in k log(k) time. steps:- 1.construct another max heap name it auxiliary heap 2.add root element of main heap to auxiliary heap 3.pop out the element from auxiliary heap and add it's 2 children to the heap 4.do step 2 and 3 till k elements have been popped out from auxiliary heap. Add the popped element's children to the auxiliary heap.