sorting - santiago - repuestos para reloj tag heuer

¿Por qué el tipo de pila tiene una complejidad de espacio de O(1)?

Question

Entiendo que tanto la ordenación rápida como la ordenada por fusión necesitan espacio auxiliar O(n) para los subarreglos temporales que se construyen, y la ordenación rápida en el lugar requiere espacio auxiliar O(log n) para los marcos de pila recursivos. Pero para la clasificación de pilas, parece que también tiene el peor de los casos de espacio auxiliar O(n) para construir la pila temporal, incluso si los nodos son solo indicadores de los elementos reales.

Me encontré con esta explanation :

Solo se requiere O (1) espacio adicional porque el montón se construye dentro de la matriz a clasificar.

Pero creo que esto significa que la matriz original ya necesariamente tuvo que implementarse como una especie de árbol. Si la matriz original era solo un vector, parece que la memoria para un montón aún tendría que ser asignada.

Answer 1

El truco interesante aquí es que heap es un árbol binario completo, solo puede usar una matriz simple, y para el elemento i, su elemento primario sería el elemento i/2 .

Answer 2

Los datos de una matriz se pueden reorganizar en un montón, en su lugar. El algoritmo para esto es en realidad sorprendentemente simple, pero no voy a entrar aquí.

Para una clasificación de pila, organiza los datos para que std::make_heap una pila en su lugar, con el elemento más pequeño en la parte posterior ( std::make_heap ). Luego intercambia el último elemento de la matriz (el elemento más pequeño del montón), con el primer elemento de la matriz (un número bastante grande), y luego baraja ese elemento grande en el montón hasta que se encuentra en una nueva posición adecuada y el montón está de nuevo, un nuevo montón mínimo, con el elemento más pequeño que queda en el último elemento de la matriz. ( std::pop_heap )

data:         1 4 7 2 5 8 9 3 6 0

make_heap:   [8 7 9 3 4 5 6 2 1 0] <- this is a min-heap, smallest on right

pop_heap(1): [0 7 9 3 4 5 6 2 1 8] <- swap first and last elements
pop_heap(2): 0 [7 9 3 4 8 6 2 5 1] <- shuffle the 8 down the heap

pop_heap(1): 0 1 [9 3 4 8 6 2 5 7] <- swap first and last elements
pop_heap(2): 0 1 [9 7 4 8 6 3 5 2] <- shuffle the 7 down the heap

etc

Por lo tanto, no es necesario almacenar datos en ningún otro lugar, excepto tal vez durante el paso de intercambio.

Para la visualización, aquí está el montón original que se muestra en una forma estándar

make_heap 
           0
     2           1
  3     4     5     6
               8   7 9
pop_heap
           8                           1                           1
     2           1               2           8               2           5 
  3     4     5     6    ->   3     4     5     6    ->   3     4     8     6 
                   7 9                         7 9                         7 9