El límite inferior de heapsort?

Question

Es bien sabido que el peor caso de tiempo de ejecución para heapsort es Ω(n lg n), pero estoy teniendo problemas para ver por qué esto es.En particular, el primer paso de heapsort (haciendo un max-heap) toma tiempo O(n).Esto es seguido por n montón de eliminaciones.Entiendo por qué cada montón de eliminación toma tiempo O(lg n);reequilibrio del montón implica una burbuja de abajo de la operación que toma tiempo O(h) en la altura de la pila, y h = O(lg n).Sin embargo, lo que no veo es por qué este segundo paso debe tomar Ω(n lg n).Parece que cualquier persona montón de cola, no necesariamente son la causa de que el nodo se trasladó a la parte superior de la burbuja todo el camino hacia abajo por el árbol.

Mi pregunta es: ¿alguien sabe de un buen inferior obligado prueba para el mejor de los casos el comportamiento de heapsort?

Answer 1

Así que hice un poco de cavar a mí misma y parece que este resultado en realidad es bastante reciente!La primera de menor obligado prueba de que puedo encontrar es a partir de 1992, a pesar de heapsort sí fue inventado en 1964.

La formal inferior obligado prueba de ello es debido a Schaffer y Sedgewick "El Análisis de Heapsort" de papel.Aquí un poco versión parafraseada de la prueba de que omite algunos de los detalles técnicos.

Para empezar, supongamos que n = 2^k - 1 para algún k, lo que garantiza que tenemos un binario completo montón.Te voy a mostrar cómo manejar este caso por separado más adelante.Porque tenemos 2^k - 1 elementos, el primer paso de heapsort, en Θ(n), la construcción de un montón de altura k.Ahora, consideremos la primera mitad de la dequeues de este montón, que quita 2^k-1 los nodos de la pila.La primera observación clave es que si usted toma el montón de partida y, a continuación, marcar todos los nodos de aquí que en realidad terminan siendo descargados, forman un subárbol de la pila (es decir,cada nodo que se obtiene eliminando tiene un padre que también se descargados).Usted puede ver esto porque si esto no fuera el caso, entonces habría algún nodo cuyo (más grande) de los padres no se obtiene eliminando a pesar de que el nodo se descargados, lo que significa que los valores están fuera de orden.

Ahora, considere cómo los nodos de este árbol son distribuidos a través de la pila.Si la etiqueta de los niveles de la pila 0, 1, 2, ..., k - 1, entonces habrá un cierto número de estos nodos en los niveles 0, 1, 2, ..., k - 2 (es decir, todo excepto el nivel inferior del árbol).En el orden de estos nodos para obtener descargados del montón, entonces tienen que obtener intercambiado hasta la raíz, y que sólo obtener intercambiado hasta un nivel en un tiempo.Esto significa que una manera de reducir la enlazado el tiempo de ejecución de heapsort sería contar el número de intercambios necesarios para llevar todos estos valores hasta la raíz.De hecho, eso es exactamente lo que vamos a hacer.

La primera pregunta que debemos responder es: ¿cuántas de las mayores 2^k-1 los nodos no están en el nivel inferior de la pila?Podemos demostrar que este no es mayor que 2^k-2 por contradicción.Supongamos que hay al menos 2^k-2 + 1 a la más grande de nodos en el nivel inferior de la pila.A continuación, cada uno de los padres de los nodos debe ser también grandes nodos en el nivel k - 2.Incluso en el mejor de los casos, esto significa que debe haber al menos 2^k-3 + 1 nodos de gran tamaño en el nivel k - 2, lo cual significa que habrá al menos 2^k-4 + 1 nodos de gran tamaño en el nivel k - 3, etc.Resumiendo, sobre todo de estos nodos, se obtiene que hay 2^k-2 + 2^k-3 + 2^k-4 + ... + 2⁰ + k nodos de gran tamaño.Pero este valor es estrictamente mayor que 2^k-1, contradiciendo el hecho de que estamos trabajando con sólo 2^k-1 los nodos de aquí.

Bueno...ahora sabemos que no son más que 2^k-2 los nodos de gran tamaño en la parte inferior de la capa.Esto significa que debe haber al menos 2^k-2 de los grandes nodos en la primera k-2 capas.Podemos ahora preguntarnos - ¿cuál es la suma, por encima de todos estos nodos, de la distancia desde el nodo hasta la raíz?Bien, si tenemos 2^k-2 los nodos se coloca en algún lugar en un montón completo, en la mayoría de los 2^k-3 de ellos puede estar en la primera k - 3 niveles, y por tanto, hay al menos 2^k-2 - 2^k-3 = 2^k-3 pesado nodos en el nivel k - 2.En consecuencia, el número total de intercambios que deben llevarse a cabo al menos (k - 2) 2^k-3.Desde n = 2^k-1, k = Θ(lg n), y por lo que este valor es Θ(n lg n) como se requiere.

Answer 2

La respuesta de observación simple es esta: los elementos en el montón son:

1
2
4
8
...
2^[log(n/4)]
and last level has between (1..2^[log(n/2)]) ==> (1,[n/2]) item, (by [] I mean Ceiling not roof)

Por ejemplo, si tiene 7 elementos:

1
2
4

Y si tienes 8 elementos:

1
2
4
1

Hay 2 árboles de montón diferentes, primero al menos n/4 - 1 elementos de un montón están en el último nivel, o no, por lo que hay al menos n/4 - 1 Elemento en el nivel antes del último, en el primer caso se necesita O((n/4 - 1) * log(n/2)) Para eliminar los elementos de último nivel del montón, y en el segundo caso toma O((n/4 - 1) * log(n/4)) Para eliminar los elementos del último nivel. Entonces, en ambos casos, se necesita Ω (n log (n)) solo para elementos N/4 - 1, por lo que es un límite inferior (fácilmente puede decir que es un límite inferior ajustado).

Answer 3

Aquí hay una solución que utiliza términos CLRS:
Comenzamos con un máximo de montaje que es un árbol binario completo con n elementos.
Podemos decir que en un binario completo hay n/2 hojas y n/2 nodos internos.
n/2 iteraciones de HEAP-SORT Eliminar el más grande n/2 elementos del montón.
Dejar S ser el conjunto del más grande n/2 elementos.
Puede haber como máximo n/4 elementos de S en las hojas ya que debe haber más n/4 de ellos en los nodos internos.
Dejar L ser estos n/4 Elementos más grandes de S que están en las hojas.
Entonces si hay n/4 elementos de S en el nivel 0 (el nivel de hojas), entonces debe haber al menos n/8 de ellos en el nivel 1.
Dejar P ser estos n/8 elementos de S que están en el nivel 1.
n/2 Las iteraciones de la oración del montón pueden dar los elementos de L un atajo a la raíz y luego fuera del montón, pero los elementos de P Debe llegar a la raíz antes de que se retiren del montón.
Entonces hay al menos (n/8)(lgn-1) Operaciones, que nos da un tiempo de ejecución de Ω (NLGN).
Ahora, por el caso de un máximo de montón que no tiene todas sus hojas en el nivel 0.
Dejar k ser el número de sus hojas en el nivel 0.
Después k iteraciones de la clasificación del montón, nos quedamos con un máximo de un árbol binario con altura lgn-1.
Podemos continuar nuestra prueba de la misma manera.
Ahora para el caso cuando hay menos de n/4 hojas de S.
Dejar k ser el número de elementos de S que están en las hojas en el nivel 0.
Si k <= n/8 entonces debe haber al menos n/8 elementos de S en el nivel 1.
Esto se debe a que puede haber un total de n/4 elementos por encima del nivel 1.
Continuamos la prueba de la misma manera.
Si k>n/8 entonces debe haber al menos n/16 elementos de S que están en el nivel 1.
Continuamos la prueba de la misma manera.
Llegamos a la conclusión de que el tiempo de ejecución de la organización del montón es Ω (NLGN).