Ordenamientos eficientes en C

HeapSort combina un montículo binario con un esquema in-place para lograr O(n log n) en todos los casos, sin memoria extra significativa. Es útil cuando queremos evitar el peor caso de QuickSort y minimizar el uso de pila.

5.1 ¿Qué es un heap?

Un heap binario es un árbol completo donde cada nodo es mayor o igual (max-heap) o menor o igual (min-heap) que sus hijos. Esto permite extraer el máximo o mínimo en O(log n).

Ver HeapSort animado

5.2 Representación en arrays

Un heap completo se mapea en un array de forma contigua:

Hijo izquierdo de i: 2 * i + 1
Hijo derecho de i: 2 * i + 2
Padre de i: (i - 1) / 2

5.3 Construcción del heap (heapify)

Construimos un max-heap en tiempo lineal recorriendo desde el último nodo interno hacia la raíz y aplicando sift-down:

void sift_down(int *arr, int n, int i) {
  int mayor = i;
  int hijo_izq = 2 * i + 1;
  int hijo_der = 2 * i + 2;

  if (hijo_izq < n && arr[hijo_izq] > arr[mayor]) {
    mayor = hijo_izq;
  }
  if (hijo_der < n && arr[hijo_der] > arr[mayor]) {
    mayor = hijo_der;
  }
  if (mayor != i) {
    int tmp = arr[i];
    arr[i] = arr[mayor];
    arr[mayor] = tmp;
    sift_down(arr, n, mayor);
  }
}

void heapify(int *arr, int n) {
  for (int i = (n / 2) - 1; i >= 0; i--) {
    sift_down(arr, n, i);
  }
}

5.4 Operación sift-down

sift_down garantiza que el nodo i cumpla la propiedad de heap, desplazando el valor hacia abajo hasta que sea mayor que sus hijos. Es la operación clave en heapify y en cada extracción.

5.5 Extracción del máximo

Para ordenar de forma ascendente con un max-heap:

Intercambiamos la raíz (máximo) con el último elemento.
Reducimos el tamaño lógico del heap.
Aplicamos sift_down en la raíz para restaurar el orden.

5.6 HeapSort paso a paso

void heapsort(int *arr, int n) {
  heapify(arr, n);
  for (int fin = n - 1; fin > 0; fin--) {
    int tmp = arr[0];
    arr[0] = arr[fin];
    arr[fin] = tmp;
    sift_down(arr, fin, 0); /* heap reducido */
  }
}

5.7 Implementación completa en C

Unificación de las funciones clave:

void sift_down(int *arr, int n, int i);
void heapify(int *arr, int n);
void heapsort(int *arr, int n);

void sift_down(int *arr, int n, int i) {
  int mayor = i;
  int hijo_izq = 2 * i + 1;
  int hijo_der = 2 * i + 2;
  if (hijo_izq < n && arr[hijo_izq] > arr[mayor]) {
    mayor = hijo_izq;
  }
  if (hijo_der < n && arr[hijo_der] > arr[mayor]) {
    mayor = hijo_der;
  }
  if (mayor != i) {
    int tmp = arr[i];
    arr[i] = arr[mayor];
    arr[mayor] = tmp;
    sift_down(arr, n, mayor);
  }
}

void heapify(int *arr, int n) {
  for (int i = (n / 2) - 1; i >= 0; i--) {
    sift_down(arr, n, i);
  }
}

void heapsort(int *arr, int n) {
  heapify(arr, n);
  for (int fin = n - 1; fin > 0; fin--) {
    int tmp = arr[0];
    arr[0] = arr[fin];
    arr[fin] = tmp;
    sift_down(arr, fin, 0);
  }
}

5.8 Costos temporales y espaciales

Tiempo: O(n log n) en todos los casos.
Memoria: O(1) adicional; trabaja in-place.
Estabilidad: no es estable.

5.9 Ventajas y desventajas

Ventajas: garantiza O(n log n) sin riesgo de peor caso cuadrático; in-place; no depende de recursión profunda.
Desventajas: no es estable; las constantes pueden ser mayores que QuickSort en promedio; acceso menos cache-friendly.

5.10 Casos donde HeapSort supera a QuickSort

Entradas adversas o diseñadas para forzar peores casos en QuickSort.
Ambientes con límites estrictos de pila o donde la recursión está restringida.
Necesidad de garantizar complejidad acotada sin riesgo de degradación.

5.11 Archivos indispensables para un proyecto en CLion

Estructura base con código listo para compilar y probar HeapSort:

/* sort.h */
void heapsort(int *arr, int n);
void printArray(const int *arr, int n);

/* sort.c */
#include <stdio.h>
#include "sort.h"

void printArray(const int *arr, int n) {
  printf("[");
  for (int i = 0; i < n; i++) {
    printf("%d", arr[i]);
    if (i + 1 < n) {
      printf(", ");
    }
  }
  printf("]\n");
}

/* heapsort.c */
#include "sort.h"

static void sift_down(int *arr, int n, int i) {
  int mayor = i;
  int hijo_izq = 2 * i + 1;
  int hijo_der = 2 * i + 2;
  if (hijo_izq < n && arr[hijo_izq] > arr[mayor]) {
    mayor = hijo_izq;
  }
  if (hijo_der < n && arr[hijo_der] > arr[mayor]) {
    mayor = hijo_der;
  }
  if (mayor != i) {
    int tmp = arr[i];
    arr[i] = arr[mayor];
    arr[mayor] = tmp;
    sift_down(arr, n, mayor);
  }
}

static void heapify(int *arr, int n) {
  for (int i = (n / 2) - 1; i >= 0; i--) {
    sift_down(arr, n, i);
  }
}

void heapsort(int *arr, int n) {
  heapify(arr, n);
  for (int fin = n - 1; fin > 0; fin--) {
    int tmp = arr[0];
    arr[0] = arr[fin];
    arr[fin] = tmp;
    sift_down(arr, fin, 0);
  }
}

/* main.c */
#include <stdio.h>
#include "sort.h"

int main(void) {
  int datos[] = {16, 7, 3, 20, 17, 8, 10, 1};
  int n = sizeof(datos) / sizeof(datos[0]);

  printf("Antes: ");
  printArray(datos, n);

  heapsort(datos, n);

  printf("Despues: ");
  printArray(datos, n);
  return 0;
}

Con esta base puedes ajustar el esquema de sift_down o instrumentar conteos de comparaciones sin cambiar la interfaz.

Retornar

5 - HeapSort