Perché siftDown è meglio di siftUp in heapify?

Question

Per costruire un albero di heap MAX, possiamo sia siftDown o siftUp, passando al setpoint iniziamo dalla radice e confrontiamolo con i suoi due figli, quindi lo sostituiamo con l'elemento più grande dei due bambini, se entrambi i bambini sono più piccoli poi ci fermiamo, altrimenti continuiamo a setacciare quell'elemento finché non raggiungiamo un nodo foglia (o, naturalmente, ancora una volta, finché quell'elemento è più grande di entrambi i suoi figli).

Ora avremo solo bisogno di fare quello n/2 volte, perché il numero di foglie è n/2, e le foglie soddisfano la proprietà heap quando finiamo di ammucchiare l'ultimo elemento sul livello prima dell'ultimo (prima delle foglie) - quindi rimarremo con gli elementi n/2 per l'heap.

Ora se usiamo siftUp, inizieremo con le foglie e alla fine avremo bisogno di ingrandire tutti gli elementi n.

La mia domanda è: non quando usiamo siftDown, stiamo facendo fondamentalmente due confronti (confrontando l'elemento ai suoi due figli), invece di un solo confronto quando si utilizza siftUp, dal momento che si confronta solo elemento alla sua uno dei genitori ? Se sì, non significherebbe che raddoppiamo la complessità e finiamo per finire con la stessa esatto complessità del setacciare?

Answer 1

realtà, costruendo un mucchio con chiamate ripetute siftDown ha una complessità di O(n) che costruirlo con chiamate ripetute siftUp ha una complessità di O(nlogn).

Ciò è dovuto al fatto che quando si utilizza siftDown, il tempo impiegato da ciascuna chiamata diminuisce con la profondità del nodo perché questi nodi sono più vicini alle foglie. Quando si utilizza siftUp, il numero di scambi aumenta con la profondità del nodo, perché se si è a profondità completa, potrebbe essere necessario passare completamente alla radice. Poiché il numero di nodi cresce esponenzialmente con la profondità dell'albero, utilizzando siftUp si ottiene un algoritmo più costoso.

Inoltre, se si utilizza un heap massimo per eseguire una sorta di ordinamento in cui si inserisce l'elemento massimo dell'heap e quindi lo si rielabora, è più semplice farlo utilizzando siftDown. È possibile reinserire nel tempo O(logn) inserendo l'elemento max, inserendo l'ultimo elemento nel nodo radice (che era vuoto perché lo si è estratto) e quindi spostandolo verso il basso fino al punto corretto.