Qual è il modo più veloce (almeno in teoria) per ordinare un heap?

Question

Un heap è un elenco in cui si applica quanto segue:

l[i] <= l[2*i] && l[i] <= [2*i+1]

per 0 <= i < len(list)

Sto cercando l'ordinamento sul posto.

Answer 1

Bene, sei già a metà di un Heap Sort, avendo i tuoi dati in un heap. Devi solo implementare la seconda parte dell'algoritmo di ordinamento dell'heap. Questo dovrebbe essere più veloce dell'uso di quicksort sull'array di heap.

Se ti senti coraggioso potresti provare a implementare smoothsort , che è più veloce di heapsort per dati quasi ordinati.

Answer 2

Usa solo l'heap-sort. È sul posto. Sarebbe la scelta più naturale.

Puoi anche usare il tuo heap e ordinarlo con qualche altro algoritmo. Successivamente ricostruisci il tuo heap dall'elenco ordinato. Quicksort è un buon candidato perché puoi essere sicuro che non funzionerà nel peggiore dei casi nell'ordine O (n & # 178;) semplicemente perché il tuo heap è già preordinato.

Potrebbe essere più veloce se la tua funzione di confronto è costosa. L'heap-sort tende a valutare abbastanza spesso la funzione di confronto.

Answer 3

L'ordinamento di un tipo di heap sul posto sembra un lavoro per Heap Sort .

Suppongo che la memoria sia limitata, un'app incorporata, forse?

Answer 4

Dato che hai già un heap, non potresti semplicemente usare la seconda fase di heap sort ? Funziona sul posto e dovrebbe essere bello ed efficiente.

Answer 5

Per l'ordinamento sul posto, segue il modo più veloce. Fai attenzione agli errori off-by-one nel mio codice. Si noti che questo metodo fornisce un elenco ordinato invertito che deve essere non ripristinato nel passaggio finale. Se si utilizza un max-heap, questo problema scompare.

L'idea generale è chiara: scambia l'elemento più piccolo (all'indice 0) con l'ultimo elemento nell'heap, sposta l'elemento verso il basso fino a quando non viene ripristinata la proprietà heap, riduci la dimensione dell'heap di uno e ripeti.

Questo non è il modo più veloce in assoluto per l'ordinamento non sul posto, come dimostra David Mackay qui - puoi fare di meglio mettendo un elemento più probabile che sia il più piccolo nella parte superiore dell'heap anziché uno dalla riga inferiore.

La complessità del tempo è T (n.log n) nel caso peggiore - n iterazioni con possibilmente log n (l'altezza dell'heap) passano attraverso il ciclo while.

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
    swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
    swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }

Answer 6

Leggi gli elementi dalla parte superiore dell'heap uno alla volta. Fondamentalmente quello che hai allora è l'heap sort.