Ordenamiento Heap con Matriz Dinámica

Introducción

En este laboratorio, aprenderá a implementar el algoritmo de clasificación Heap Sort utilizando matrices dinámicas en C++. El heap sort es un algoritmo de clasificación basado en comparaciones que funciona dividiendo la entrada en una región clasificada y una región no clasificada y reduciendo iterativamente la región no clasificada extrayendo el elemento más grande o más pequeño y moviéndolo a la región clasificada.

Skills Graph

Creando la matriz dinámica

Creamos un nuevo archivo llamado main.cpp en el directorio ~/project con el siguiente comando:

touch ~/project/main.cpp

Primero, crearemos una matriz dinámica para almacenar elementos. Usaremos el operador new para asignar dinámicamente memoria durante la ejecución del programa.

int* arr;
arr = new int[size];

Función heapify

A continuación, crearemos la función heapify() para reordenar los elementos en el arreglo. El propósito de la función heapify() es mantener la propiedad de heap, lo que significa que cada nodo es mayor o igual que sus hijos.

void heapify(int* arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest!= i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

Función de clasificación Heap

Después de implementar la función heapify(), crearemos la función heapSort() para ordenar el arreglo en orden ascendente.

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);
    }
}

Función principal

Finalmente, crearemos la función main() para leer los elementos del usuario y mostrar el arreglo ordenado utilizando el algoritmo de clasificación Heap.

int main() {
    int size;
    cout << "Enter the number of elements: ";
    cin >> size;

    int* arr;
    arr = new int[size];

    cout << "Enter the elements: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }

    heapSort(arr, size);

    cout << "Sorted Array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    delete[] arr;
    return 0;
}

Resumen

En este laboratorio, aprendiste cómo implementar el algoritmo de clasificación Heap utilizando matrices dinámicas en C++. También aprendiste sobre la creación de una matriz dinámica, la transformación de la matriz en un heap y la clasificación de la matriz para mostrar la matriz ordenada en orden ascendente. Sigue las instrucciones para ejecutar el código de ejemplo y practicar la implementación del algoritmo de clasificación Heap.