Ordenamiento por montículos

1. Algoritmo de ordenamiento por montículos
2. Ejemplo de ordenamiento por montículos
3. Implementación del Algoritmo de ordenamiento por montículos
4. Complejidad del algoritmo de ordenamiento por montículos

La ordenamiento por montículos es un algoritmo de ordenación basado en la comparación. Su nombre proviene de la estructura de datos del montón utilizada en el algoritmo. El montón es una estructura de datos especial basada en un árbol binario. Tiene las siguientes dos propiedades:

• Es un árbol binario completo con todos los niveles llenos excepto el último. El último puede estar parcialmente lleno, pero todos los nodos están lo más a la izquierda posible.
• Todos los nodos padres son más pequeños/más grandes que sus dos nodos hijos. Si son más pequeños, el montón se llama min-heap, y si son más grandes, entonces el montón se llama max-heap. Para un índice dado i, el padre está dado por (i-1)/2, el hijo izquierdo está dado por (2*i+1) y el hijo derecho está dado por (2*i+2).

La ordenación en pila funciona de forma muy similar a la ordenación por selección. Selecciona el elemento máximo del array usando max-heap y lo coloca en su posición al final del array. Hace uso de un procedimiento llamado heapify() para construir el montón.

Algoritmo de ordenamiento por montículos

Supongamos que tenemos un array A[] sin ordenar que contiene n elementos.

HeapSort()

Heapify()

Ejemplo de ordenamiento por montículos

Supongamos que tenemos el array (5, 3, 4, 2, 1, 6). Vamos a ordenarlo utilizando el algoritmo de ordenación del montón.

Después de construir el montón, obtenemos el array como: (6 3 5 2 1 4).

• Primera Iteración:

• Segunda Iteración:

• Tercera Iteración:

• Cuarta Iteración:

• Quinta Iteración:

• Sexta Iteración:

Obtenemos el array ordenado como : (1,2,3,4,5,6)

Implementación del Algoritmo de ordenamiento por montículos

#include <bits/stdc++.h>
using namespace std;

void heapify(int arr[], int n, int i) {
  int parent = i;
  int leftChild = 2 * i + 1;
  int rightChild = 2 * i + 2;

  if (leftChild < n && arr[leftChild] > arr[parent]) parent = leftChild;

  if (rightChild < n && arr[rightChild] > arr[parent]) parent = rightChild;

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

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

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  heapSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complejidad del algoritmo de ordenamiento por montículos

Complejidad de tiempo

• Caso medio

La altura de un árbol binario completo con n elementos es como máximo logn. Por lo tanto, la función heapify() puede tener un máximo de logn comparaciones cuando un elemento se mueve de la raíz a la hoja. La función Heapify() es llamada para n/2 elementos haciendo que la complejidad de tiempo total para la primera etapa sea n/2*logn o T(n) = nlogn.

La función HeapSort() requiere el peor tiempo de logn para cada elemento, y n elementos hacen que su complejidad de tiempo sea también nlogn. Tanto la complejidad temporal de la construcción del montón como la del ordenamiento del montón se suman y nos dan la complejidad resultante como nlogn. Por lo tanto, la complejidad temporal total es del orden de [Big Theta]: O(nlogn).

• El peor caso

La complejidad temporal en el peor caso es [Big O]: O(nlogn).

• El mejor caso

La complejidad temporal en el mejor de los casos es [Big Omega]: O(nlogn). Es la misma que la complejidad temporal del peor caso.

Complejidad espacial

La complejidad espacial del algoritmo de ordenación del montón es O(1) porque no se necesita más memoria que la de las variables temporales.