Según Wikipedia, el algoritmo en el lugar se define a continuación:
En informática, un algoritmo in situ es un algoritmo que transforma la entrada sin utilizar una estructura de datos auxiliar. Sin embargo, se permite una pequeña cantidad de espacio de almacenamiento adicional para las variables auxiliares. La entrada generalmente se sobrescribe con la salida a medida que se ejecuta el algoritmo. El algoritmo in situ actualiza la secuencia de entrada solo mediante el reemplazo o el intercambio de elementos. Un algoritmo que no está en el lugar a veces se llama no en el lugar o fuera de lugar.
Ahora, la ordenación del montón está en su lugar porque la matriz no ordenada se convierte primero en un montón sin crear matrices adicionales ni ninguna otra estructura de datos cuyo tamaño dependa del tamaño de la matriz original y luego el montón se reduce a una matriz ordenada.
- ¿Cuáles son algunos URI de buen código de ejemplo que utilizan algoritmos STL (aparte de la ordenación)?
- ¿Existe evidencia de que el algoritmo de sugerencia de música basada en el genoma de Pandora es mejor que los algoritmos de recomendación estándar?
- ¿Cómo debo explicar Hashing a un niño de 4 años?
- ¿Se aplican las estructuras de datos y algoritmos para C / C ++ a JavaScript?
- ¿Por qué ocurre el peor de los casos en Max-Heapify cuando la fila final del árbol está medio llena?
Por lo tanto, considere la siguiente matriz que debe clasificarse. Al considerar las siguientes reglas:
1. El elemento en el índice 0 es la raíz.
2. Para cualquier nodo del montón en el índice i, incluido el nodo raíz (i = 0):
Índice de niño izquierdo = 2 * i + 1
Índice de niño derecho = 2 * i + 2
Padre del nodo = (i-1) / 2
la matriz se puede representar como el siguiente árbol binario completo:
La matriz anterior se convierte en un montón máximo como se muestra a continuación (puede consultar los pasos detallados del algoritmo desde aquí – Algoritmo de clasificación – Ordenar montón) –
Ahora, una vez que hemos creado el montón máximo, usamos la misma memoria utilizada por la matriz para convertir la matriz en una matriz ordenada.
Entonces, aunque su algoritmo funcionará en una estructura de datos de almacenamiento dinámico, pero no creará ninguna memoria nueva para el almacenamiento dinámico, utilizará la misma matriz para todas las operaciones.
Esa es la razón por la cual la ordenación del montón es un algoritmo de ordenación in situ.
Fuente de imagen y algoritmo: IDeserve – Algoritmo de clasificación – Clasificación de montón
