¿Listar valores en un montón binario en orden ordenado utilizando la búsqueda de ancho de banda?

Question

Actualmente estoy leyendo this paper y en la página cinco, se describen las propiedades de montones binarios que considera que son de dominio público. Sin embargo, uno de los puntos que hacen es algo que no he visto antes y que no tiene sentido. Los autores afirman que si le dan un montón binario equilibrado, puede enumerar los elementos de ese montón en orden ordenado en el tiempo O (log n) por elemento utilizando una búsqueda estándar de ancho de banda. Aquí está su redacción original:

en un montón equilibrada, cualquier nuevo elemento puede ser inserta en el tiempo logarítmica. Podemos enumerar los elementos de un montón en orden por peso, tomando un tiempo logarítmico de para generar cada elemento, simplemente usando la primera búsqueda de ancho.

No estoy seguro de lo que los autores quieren decir con esto. Lo primero que viene a la mente cuando dicen "búsqueda de amplitud" sería una búsqueda de amplitud de los elementos de árbol que comienzan en la raíz, pero no se garantiza que los elementos estén en orden ordenado, ni se necesita tiempo logarítmico por elemento Por ejemplo, la ejecución de un BFS en este min heap produce los elementos fuera de orden no importa cómo se rompen los lazos:

   1 
      /\ 
      10 100 
     /\ 
     11 12 

Esto siempre enumera 100 antes de 11 o 12, que es claramente erróneo.

¿Echo de menos algo? ¿Hay una búsqueda simple de amplitud que puede realizar en un montón para obtener los elementos en orden ordenado usando tiempo logarítmico cada uno? Claramente, puedes hacer esto modificando de forma destructiva el montón eliminando el elemento mínimo cada vez, pero la intención de los autores parece ser que esto se puede hacer de forma no destructiva.

Answer 1

Usted puede obtener los elementos en el orden establecido por la que atraviesa el montón con una cola de prioridad (que requiere otro montón!). Supongo que esto es a lo que él se refiere como una "primera búsqueda de amplitud".

creo que debería ser capaz de entenderlo (dada su representante en algoritmos) pero básicamente la clave de la cola de prioridad es el peso de un nodo. Empuja la raíz del montón a la cola de prioridad. Entonces:

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

No estoy realmente seguro (en absoluto) si esto es lo que se refería pero vagamente se ajustaba a la descripción y no ha habido mucha actividad, así que pensé que también podría ponerlo allí afuera.

Answer 2

En caso de que sepa que todos los elementos inferiores a 100 están a la izquierda puede ir a la izquierda, pero en cualquier caso, incluso si llega a 100, puede ver que no hay elementos a la izquierda para salir. En cualquier caso, vaya desde el nodo (o cualquier otro nodo) en el peor de los casos dos veces antes de darse cuenta de que no hay ningún elemento que esté buscando. Que los hombres que vayas en este árbol a lo más 2 * log (N) veces. Esto se simplifica para registrar (N) la complejidad.

El punto es que incluso si "la pata" y que atraviesan al nodo "mal" que vaya ese nodo en el peor una vez.

EDIT
Así es como funciona heapsort. Puedes imaginar que tienes que reconstruir el montón usando la complejidad N (log n) cada vez que sacas el elemento superior.