Elenco dei valori in un heap binario nell'ordine ordinato utilizzando la ricerca in ampiezza?

Question

Attualmente sto leggendo this paper e nella pagina cinque, discute le proprietà degli heap binari che considera essere di dominio pubblico. Tuttavia, uno dei punti che fanno è qualcosa che non ho visto prima e non può dare un senso. Gli autori sostengono che se viene fornito un heap binario bilanciato, è possibile elencare gli elementi di quell'heap in ordine ordinato in tempo O (log n) per elemento utilizzando una ricerca standard in larghezza. Ecco la loro dicitura originale:

In un heap bilanciato, qualsiasi nuovo elemento può essere inserito in tempo logaritmico. Possiamo elencare gli elementi di un heap in ordine di peso, prendendo il tempo logaritmico per generare ciascun elemento, semplicemente utilizzando la ricerca per ampiezza prima.

Non sono sicuro del significato degli autori. La prima cosa che viene in mente quando si dice "ricerca in ampiezza" sarebbe una ricerca in ampiezza degli elementi dell'albero a partire dalla radice, ma non è garantito elencare gli elementi in ordine, né richiede tempo logaritmico per elemento Ad esempio, l'esecuzione di un BFS su questo min-heap produce gli elementi su ordine non importa quanto si rompere i legami:

   1 
      /\ 
      10 100 
     /\ 
     11 12 

elencati nel presente sempre il 100 prima di 11 o 12, che è chiaramente sbagliata.

Mi manca qualcosa? Esiste una semplice ricerca in ampiezza che è possibile eseguire su un heap per ottenere gli elementi in ordine ordinato utilizzando il tempo logaritmico ciascuno? Chiaramente puoi farlo modificando distruttivamente l'heap rimuovendo ogni volta l'elemento minimo, ma l'intento degli autori sembra essere che questo può essere fatto in modo non distruttivo.

Answer 1

È possibile ottenere gli elementi in ordine ordinando attraversando l'heap con una coda di priorità (che richiede un altro heap!). Immagino che questo sia ciò a cui si riferisce come una "ricerca per ampiezza".

Penso che dovresti essere in grado di capirlo (dato il tuo rappresentante in algoritmi) ma fondamentalmente la chiave della coda di priorità è il peso di un nodo. Si spinge la radice dell'heap sulla coda di priorità. Poi:

while pq isn't empty 
    pop off pq 
    append to output list (the sorted elements) 
    push children (if any) onto pq 

Io non sono davvero sicuro (a tutti), se questo è ciò che si riferiva, ma vagamente montato la descrizione e non c'è stata molta attività così ho pensato che potrei pure metterlo là fuori.

Answer 2

Nel caso in cui si sappia che tutti gli elementi inferiori a 100 sono a sinistra si può andare a sinistra, ma in ogni caso anche se si arriva a 100 si vede che non ci sono elementi a sinistra in modo da uscire. In ogni caso, vai dal nodo (o da qualsiasi altro nodo) nel peggiore dei casi due volte prima di rendersi conto che non ci sono elementi che stai cercando. Rispetto agli uomini che vai in questo albero al massimo 2 * log (N) volte. Questo è semplificato per accedere alla complessità (N).

Il punto è che anche se si "rovina" e si passa al nodo "errato" si passa quel nodo al peggio una volta.

EDIT
Questo è il modo in cui funziona heapsort. È possibile immaginare che è necessario ricostruire l'heap utilizzando la complessità N (log n) ogni volta che si estrae l'elemento principale.