sorting - heapify - ¿Por qué no es estable Heapsort?
heapsort python (5)
Estoy tratando de entender por qué Heapsort no es estable. He buscado en Google, pero no he encontrado una buena explicación intuitiva.
Entiendo la importancia de la clasificación estable: nos permite clasificar en función de más de una clave, lo que puede ser muy beneficioso (es decir, realizar varias clasificaciones, cada una basada en una clave diferente. Dado que cada tipo conservará el orden relativo de los elementos, Las clasificaciones anteriores pueden sumarse para dar una lista final de elementos ordenados por criterios múltiples). Sin embargo, ¿por qué heapsort no preservaría esto también?
¡Gracias por tu ayuda!
Estable significa que si los dos elementos tienen la misma clave, permanecen en el mismo orden o posición. Pero ese no es el caso para la clase Heap.
Heapsort no es estable porque las operaciones en el montón pueden cambiar el orden relativo de elementos iguales.
Desde here
Cuando se ordena (en orden ascendente), el primer montón acumula el máximo del elemento más grande y lo coloca en el último de la lista. Por lo tanto, el elemento que se ha seleccionado primero, permanece en último lugar y el elemento que se ha seleccionado en segundo lugar permanece en el segundo último elemento de la lista ordenada.
Nuevamente, el procedimiento Build-Max-Heap funciona de manera tal que preserva el orden del mismo valor (ej: 3a, 3b) en la construcción del árbol de pila. Para extraer el elemento máximo, también funciona desde la raíz e intenta preservar la estructura del árbol (excepto el cambio de Heapify).
Entonces, lo que sucede, para los elementos con el mismo valor [3a, 3b], el heapsort selecciona 3a antes de 3b pero coloca 3a a la derecha de 3b. Entonces, como la lista está ordenada en orden ascendente, obtenemos 3b antes de 3a en la lista.
Si intenta heapsort con (3a, 3b, 3b) entonces puede visualizar la situación.
Heap ordenar ejemplo inestable
Considere la matriz 21 20a 20b 12 11 8 7 (ya en formato max-heap)
aquí 20a = 20b solo para diferenciar el orden en que los representamos como 20a y 20b
Mientras que heapsort first 21 se elimina y se coloca en el último índice, 20a se elimina y se coloca en el último, pero un índice y 20b en el último, pero el índice de dos, así que después de la ordenación del montón, la matriz parece:
7 8 11 12 20b 20a 21 .
No conserva el orden de los elementos y por lo tanto no puede ser estable
La secuencia final de los resultados de heapsort proviene de la eliminación de elementos del montón creado en orden de tamaño puro (basado en el campo clave).
Cualquier información sobre el orden de los elementos en la secuencia original se perdió durante la etapa de creación del montón, que se produjo primero.
Sé que esta es una respuesta tardía pero agregaré mis 2 centavos aquí. Considere una matriz simple de 3 enteros. 2,2,2 ahora, si construye un montón máximo utilizando la función construir el montón máximo, encontrará que la matriz que almacena la entrada no ha cambiado, ya que ya está en la forma de montón máximo. Ahora, cuando colocamos la raíz del árbol al final de la matriz en la primera iteración de la ordenación del montón, la estabilidad de la matriz ya se ha ido. Así que aquí tienes un ejemplo simple de la inestabilidad de la clase de pila.
Supongamos que se toma una matriz de tamaño n (valor arbitrario) y si hay dos elementos consecutivos (se supone 15) en el montón y si sus índices primarios tienen valores como 4 y 20. (este es el orden real (... 4,20 , ....., 15,15 .....). El orden relativo de 4 y 1st 15 sigue siendo el mismo, pero como 20> 15, el 2nd 15 viene al frente (swap) como se define en el algoritmo de clasificación de pila, el El orden relativo se ha ido.