Introducción a la ordenación del montón en C ++
Heapsort es una de las técnicas de clasificación basadas en la comparación y forma parte de la selección. Donde la ordenación se define como organizar conjuntos de datos en un orden específico utilizando un valor único conocido como elemento clave en la lista dada. El término clasificación se introdujo a medida que las personas llegaban a conocer la importancia de buscar cualquier elemento en cualquier conjunto de información dado; de lo contrario, sería muy difícil buscar cualquier registro si no estuviera ordenado ni ordenado.
Hay muchas técnicas diferentes involucradas en la clasificación, cada una con su eficiencia respectiva en el tiempo necesario para clasificar los datos dados y los requisitos de espacio en la memoria. Son de tipo burbuja, tipo de inserción, tipo de selección, tipo rápido, tipo de fusión y tipo de montón.
¿Qué es la ordenación del montón?
Heapsort es un enfoque de clasificación basado en la estructura de datos de almacenamiento dinámico binario similar a la clasificación de selección donde primero obtenemos el conjunto máximo de datos y lo colocamos al final y continuamos con el resto de los elementos.
Heapsort como su propio nombre sugiere. Primero construye el montón de elementos de datos de la matriz sin clasificar dada, y luego comprueba el elemento más grande y lo coloca al final de la matriz parcialmente ordenada. Nuevamente reconstruye el montón, busca la siguiente pieza de registro más grande y la coloca en el siguiente espacio vacío desde el final de la disposición de registros medio ordenada. Este proceso se repite hasta que no quedan elementos en el montón. Esta técnica requiere dos matrices, una para almacenar el montón y la otra para una matriz ordenada.
Algoritmo de ordenación del montón en C ++
- En primer lugar, elija root como un elemento elevado del conjunto de elementos de información dado para crear un montón máximo.
- Reconstruya el montón colocando o intercambiando la raíz con el último elemento.
- El tamaño del montón ahora se reducirá en 1.
- Luego, nuevamente hacemos el montón con los elementos restantes y continuamos hasta que el tamaño del montón se reduce a 1.
Ejemplo de ordenación del montón en C ++
Esta técnica utiliza un montón binario que se construye utilizando un árbol binario completo donde el nodo raíz es mayor que sus dos nodos hijos.
Considere la matriz dada de conjuntos de datos.
Vayamos de acuerdo con el algoritmo. Dice seleccionar el elemento más alto como raíz y construir el montón máximo.
1. Primera iteración
Ahora la matriz tendrá la forma:
Ahora la matriz ordenada tendrá la forma:
El tamaño del montón se reducirá en 1, ahora 6-1 = 5.
2. Segunda iteración
Entonces ahora el montón se ve así:
La matriz tiene la forma:
La matriz ordenada será:
El tamaño del montón se reducirá en 1, ahora 5-1 = 4.
3. Tercera iteración
El nuevo montón se ve así:
La matriz tiene la forma:
La matriz ordenada será:
El tamaño del montón se reducirá en 1, ahora 4-1 = 3.
4. Cuarta iteración
El nuevo montón se ve así:
La matriz tiene la forma:
La matriz ordenada será:
El tamaño del montón se reducirá en 1, ahora 3-1 = 2.
5. Quinta iteración
El nuevo montón se ve así:
La matriz tiene la forma:
La matriz ordenada será:
El tamaño del montón se reducirá en 1, ahora 2-1 = 1.
6. Última iteración
El nuevo montón se ve así:
La matriz tiene:
4 4
Desde el algoritmo, hemos llevado a cabo todos los pasos hasta que el tamaño de almacenamiento dinámico sea 1. Así que ahora tenemos la matriz ordenada:
Por lo tanto, la matriz ordenada del montón máximo está en orden ascendente. Si necesitamos la matriz ordenada en orden descendente, siga los pasos anteriores con un montón mínimo.
El programa C ++ para la ordenación del montón es el siguiente:
#include
using namespace std;
void heapify(int arr(), int n, int i)
(
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l arr(largest))
largest = l;
if (r arr(largest))
largest = r;
if (largest != i) (
swap(arr(i), arr(largest));
heapify(arr, n, largest);
)
)
void heapSort(int arr(), int n)
(
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
(
swap(arr(0), arr(i));
heapify(arr, i, 0);
)
)
void printArray(int arr(), int n)
(
for (int i = 0; i < n; ++i)
cout << arr(i) << " ";
cout << "\n";
)
int main()
(
int arr() = ( 5, 18, 4, 13, 10, 7);
int n = sizeof(arr) / sizeof(arr(0));
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
)
Salida:
Conclusión
Heapsort es la técnica basada en comparación que es la mejora de la selección de selección. La ordenación de montón utiliza la selección del elemento más alto o más bajo en la matriz dada para ordenar en orden ascendente o descendente, respectivamente, con el montón máximo o mínimo. Realice este proceso hasta que obtengamos uno como tamaño de almacenamiento dinámico. Esta técnica de clasificación también se utiliza para encontrar el elemento más grande y más bajo en la matriz. La técnica de clasificación de montón es más eficiente y más rápida que la técnica de clasificación de selección.
Artículos recomendados
Esta es una guía para la ordenación del montón en C ++. Aquí discutimos qué es el montón en c ++, trabajando con su algoritmo y Ejemplo. También puede consultar los siguientes artículos para obtener más información.
- Heap Sort en C
- Heap Ordenar en Java
- Sobrecarga en C ++
- Punteros en C ++
- Sobrecarga en Java