Limite inferiore heapsort?

Question

E 'ben noto che il runtime peggiore per heapsort è O (n lg n), ma sto avendo difficoltà a vedere perché questo è. In particolare, la prima fase di heapsort (fare un max-heap) richiede tempo T (n). Questo è seguito da eliminazioni n heap. Capisco perché ogni eliminazione mucchio richiede tempo O (lg n); riequilibrare il cumulo comporta un'operazione bolla-down che richiede tempo O (h) in altezza del mucchio, e h = O (lg n). Tuttavia, ciò che non vedo il motivo per cui è questa seconda fase dovrebbe prendere O (n lg n). Sembra che ogni individuo dequeue mucchio non sarebbe necessariamente causa il nodo spostato verso l'alto a bollire fino in fondo l'albero.

La mia domanda è -? Qualcuno sa di prova di un buon inferiore limite per il comportamento nel caso migliore di heapsort

Answer 1

Così ho fatto un po 'di scavare me stesso e sembra che questo risultato in realtà è piuttosto recente! La prova prima inferiore-bound che posso trovare è dal 1992, anche se heapsort stesso è stato inventato nel 1964.

La prova più bassa-bound formale è causa di Schaffer e Sedgewick del giornale "L'analisi di Heapsort". Ecco una versione leggermente parafrasata della prova che omette alcuni dei dettagli tecnici.

Per cominciare, supponiamo che n = 2 ^k - 1 per qualche k, che garantisce che abbiamo un mucchio binario completo. Vi mostrerò come gestire questo caso a parte in seguito. Perché abbiamo 2 ^k - 1 elementi, il primo passaggio di heapsort sarà, a T (n), costruire un mucchio di altezza k. Ora, prendere in considerazione la prima metà degli Ritiri dalla coda da questo mucchio, che rimuove 2 ^k-1 nodi dal mucchio. La prima osservazione chiave è che se si prende il mucchio di partenza e poi contrassegnare tutti i nodi qui che in realtà finiscono per essere rimosse dalla coda, formano una sottostruttura del mucchio (vale a dire tutti i nodi che get accodamento ha un genitore che viene anche rimosse dalla coda). Si può vedere questo perché se così non fosse il caso, allora non ci sarebbe qualche nodo la cui (più grande) genitore non ha ottenuto rimosse dalla coda anche se il nodo stesso è stato eliminato dalla coda, il che significa che i valori sono fuori uso.

Ora, considerare come i nodi di questo albero sono distribuiti in tutto il mucchio. Se si etichetta i livelli del mucchio 0, 1, 2, ..., k - 1, allora ci sarà un numero di questi nodi in livelli 0, 1, 2, ..., k - 2 (che è, tutto tranne il livello inferiore della struttura). Affinché questi nodi per ottenere rimossa da mucchio, allora devono ottenere scambiato fino alla radice, e si ottiene solo scambiati di un livello alla volta. Ciò significa che un modo per abbassare rilegati il ??tempo di esecuzione heapsort sarebbe per contare il numero di scambi necessarie per portare tutti questi valori fino alla radice. In realtà, questo è esattamente quello che andremo a fare.

La prima domanda che dobbiamo risposta è - come molti dei più grandi 2 ^k-1 nodi non sono del livello di fondo del mucchio? Siamo in grado di dimostrare che questo non è maggiore di 2 ^k-2 per assurdo. Supponiamo che ci siano almeno 2 ^k-2 + 1 dei maggiori nodi del livello inferiore del mucchio. Quindi ciascuno dei genitori di quei nodi deve essere anche grandi nodi a livello k - 2. Anche nel migliore dei casi, ciò significa che ci deve essere almeno 2 ^k-3 + 1 grandi nodi a livello k - 2, che poi significa che ci sarebbero almeno 2 ^k-4 + 1 grandi nodi livello k - 3, ecc Sommando su tutti questi nodi, otteniamo che ci sono 2 ^k-2 + 2 ^k-3 + 2 ^k-4 + ... + 2 ⁰ + k grandi nodi. Ma questo valore è strettamente maggiore di 2 ^k-1 , in contraddizione con il fatto che stiamo lavorando con solo 2 ^k-1 nodi qui.

Va bene ... ora sappiamo che ci sono al massimo 2 ^k-2 di grandi dimensioni nodi nello strato inferiore. Ciò significa che ci deve essere di almeno 2 ^k-2 dei grandi nodi nei primi k-2 strati. Ora chiediamo - Qual è la somma, su tutti questi nodi, della distanza da quel nodo alla radice? Beh, se abbiamo 2 ^k-2 nodi da qualche parte posizionata in un mucchio completo, allora al massimo 2 ^k-3 di essi possono essere nel primo k - 3 livelli, e quindi ci sono almeno 2 ^k-2 - 2 ^k-3 = 2 ^k-3 nodi pesanti a livello k - 2. Conseguentemente , il numero totale di swap che devono essere eseguite sono almeno (k - 2) 2 ^k-3 . Poiché n = 2 ^k -1, k = T (lg n), e quindi questo valore è T (n lg n) come richiesto.

Answer 2

risposta osservazione semplice è questa: Le voci nel mucchio sono:

1
2
4
8
...
2^[log(n/4)]
and last level has between (1..2^[log(n/2)]) ==> (1,[n/2]) item, (by [] I mean Ceiling not roof)

Per esempio, se si dispone di 7 articolo:

1
2
4

e se si dispone di 8 articolo:

1
2
4
1

Non c'è 2 altro albero mucchio, prima almeno n / 4 - 1 voci di un cumulo sono in ultimo livello, o no, per cui v'è almeno voce n/4 - 1 a livello prima ultimo, nel primo caso ci vuole O((n/4 - 1) * log(n/2)) per rimuovere elementi ultimi livello provenienti mucchio, e nel secondo caso si impiegano O((n/4 - 1) * log(n/4)) per rimuovere gli articoli dal pre ultimo livello. Quindi, in entrambi i casi ci vuole O (n log (n)) solo per n / 4 - 1 elementi, quindi è un limite inferiore (facilmente può dire che è stretto il limite inferiore).

Answer 3

Ecco una soluzione che usi termini CLR:
Si comincia con un max-heap è un albero binario completo con elementi n.
Possiamo dire che in un binario completo ci sono foglie n/2 e nodi interni n/2.
iterazioni n/2 di HEAP-SORT rimuovono più grandi elementi n/2 dal mucchio.
Lasciate S l'insieme dei più grandi elementi n/2.
Non ci può essere al massimo gli elementi n/4 da S nelle foglie in quanto ci deve essere ulteriore n/4 di loro nei nodi interni.
Lasciate che sia L questi n/4 più grandi elementi di S che sono nelle foglie.
Quindi, se ci sono elementi da n/4 S a livello 0 (il livello foglie) allora ci deve essere almeno n/8 di loro a livello 1.
Lasciate che sia P questi elementi n/8 da S che sono al livello 1.
iterazioni n/2 di HEAP-SORT possono dare gli elementi da L una scorciatoia alla radice e quindi fuori dal mucchio, ma gli elementi da P deve fare fino alla radice prima di essere rimossi dal mucchio.
Quindi ci sono operazioni (n/8)(lgn-1) meno, che ci dà un tempo di esecuzione di O (nlgn).
Ora, per il caso di un max-heap che non dispone di tutte le sue foglie a livello 0.
Lasciate k sia il numero delle sue foglie a livello 0.
Dopo iterazioni k di HEAP-SORT, ci ritroviamo con un max-heap che è un albero binario completo di altezza lgn-1.
Siamo in grado di continuare la nostra prova nello stesso modo.
Ora, per il caso in cui ci sono meno di foglie n/4 da S.
Lasciate k sia il numero di elementi da S che sono le foglie a livello 0.
Se k <= n/8 allora ci deve essere almeno elementi n/8 da S al livello 1.
Questo perché non ci può essere un totale di elementi n/4 sul livello 1.
Continuiamo la prova nello stesso modo.
Se k>n/8 allora ci deve essere almeno elementi n/16 da S che sono al livello 1.
Continuiamo la prova nello stesso modo.
Concludiamo che il tempo di esecuzione di HEAP-SORT è O (nlgn).