Heap Sort
Última actualización
Heap sort trata el arreglo como un heap binario. Primero construye un max-heap, de modo que el elemento más grande queda en la raíz (índice 0). Luego intercambia repetidamente la raíz con el último elemento no ordenado - fijando el máximo en su lugar - y hunde la nueva raíz para restaurar la propiedad del heap. Pulsa reproducir arriba para ver cómo se construye el heap y las extracciones.
Heap sort garantiza un tiempo de O(n log n) como merge sort, pero ordena en el sitio con solo O(1) de espacio adicional. No es estable y suele tener peor comportamiento de caché que quicksort, por lo que se elige a menudo cuando importan tanto una cota garantizada como una memoria constante.
Complejidad temporal y espacial
| Caso | Complejidad | Notas |
|---|---|---|
| Mejor caso | O(n log n) | Construcción + n extracciones |
| Caso promedio | O(n log n) | Orden aleatorio |
| Peor caso | O(n log n) | Garantizado |
| Espacio | O(1) | En el sitio |
| Estable | No | El hundimiento reordena elementos iguales |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Construir un max-heap a partir del arreglo (hundir desde el último padre). |
| 2 | Intercambiar la raíz (máximo) con el último elemento del heap. |
| 3 | Reducir el heap en uno - ese último hueco ya está ordenado. |
| 4 | Hundir la nueva raíz para restaurar la propiedad del max-heap. |
| 5 | Repetir hasta que el heap tenga un solo elemento. |
Ejemplo resuelto
Ordenando [3, 1, 6, 5, 2, 4]. La barra | marca el límite entre el heap que se reduce y la cola ordenada:
| Pasada | Arreglo | Acción |
|---|---|---|
| Construir heap | [6, 5, 4, 1, 2, 3] | Hundir desde el último padre para construir el max-heap; 6 queda ahora en la raíz. |
| 1 | [5, 3, 4, 1, 2 | 6] | Intercambiar la raíz 6 con el último hueco, reducir el heap y hundir 3. |
| 2 | [4, 3, 2, 1 | 5, 6] | Sacar la raíz 5, luego hundir 2 para que 4 suba a la raíz. |
| 3 | [3, 1, 2 | 4, 5, 6] | Sacar la raíz 4, luego hundir 1 para que 3 suba a la raíz. |
| 4 | [2, 1 | 3, 4, 5, 6] | Sacar la raíz 3; 2 ya cumple la propiedad del heap. |
| 5 | [1 | 2, 3, 4, 5, 6] | Sacar la raíz 2; queda un elemento, así que el arreglo está ordenado. |
Cuándo usar heap sort
| Úsalo cuando | Evítalo cuando |
|---|---|
Necesitas un peor caso garantizado de O(n log n) sin riesgo de O(n²). | Necesitas un ordenamiento estable que preserve el orden de claves iguales. |
La memoria es escasa - ordena en el sitio con solo O(1) de espacio adicional. | Importa el rendimiento de caché y los datos caben en memoria - quicksort suele ser más rápido. |
| Ya mantienes un heap (p. ej. una cola de prioridad) sobre los datos. | Quieres el menor número de comparaciones - merge sort y quicksort suelen hacer menos en la práctica. |
| Una entrada no confiable podría provocar el peor caso de quicksort y no puedes aleatorizar. | Los datos están casi ordenados - insertion sort se ejecuta en tiempo casi lineal sobre ellos. |
Código de Heap Sort
Una implementación limpia y ejecutable de Heap Sort en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Heap Sort en Python
Python
1def heap_sort(a):2 n = len(a)3 # Build a max-heap, deepest parent first4 for i in range(n // 2 - 1, -1, -1):5 sift_down(a, i, n)6 # Repeatedly move the max to the end and shrink the heap7 for end in range(n - 1, 0, -1):8 a[0], a[end] = a[end], a[0]9 sift_down(a, 0, end)10 return a11
12
13def sift_down(a, i, size):14 while True:15 largest = i16 left, right = 2 * i + 1, 2 * i + 217 if left < size and a[left] > a[largest]:18 largest = left19 if right < size and a[right] > a[largest]:20 largest = right21 if largest == i:22 return23 a[i], a[largest] = a[largest], a[i]24 i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)Código de Heap Sort en JavaScript
JavaScript
1function heapSort(a) {2 const n = a.length;3 // Build a max-heap, then repeatedly move the max to the end4 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5 for (let end = n - 1; end > 0; end--) {6 [a[0], a[end]] = [a[end], a[0]];7 siftDown(a, 0, end);8 }9 return a;10}11
12function siftDown(a, i, size) {13 while (true) {14 const left = 2 * i + 1;15 const right = 2 * i + 2;16 let largest = i;17 if (left < size && a[left] > a[largest]) largest = left;18 if (right < size && a[right] > a[largest]) largest = right;19 if (largest === i) return;20 [a[i], a[largest]] = [a[largest], a[i]];21 i = largest;22 }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));Código de Heap Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void heapSort(int[] arr) {5 int n = arr.length;6 // Build a max-heap, deepest parent first7 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8 // Repeatedly move the max to the end and shrink the heap9 for (int end = n - 1; end > 0; end--) {10 swap(arr, 0, end);11 siftDown(arr, 0, end);12 }13 }14
15 static void siftDown(int[] arr, int i, int size) {16 while (true) {17 int largest = i, l = 2 * i + 1, r = 2 * i + 2;18 if (l < size && arr[l] > arr[largest]) largest = l;19 if (r < size && arr[r] > arr[largest]) largest = r;20 if (largest == i) return;21 swap(arr, i, largest);22 i = largest;23 }24 }25
26 static void swap(int[] arr, int a, int b) {27 int tmp = arr[a];28 arr[a] = arr[b];29 arr[b] = tmp;30 }31
32 public static void main(String[] args) {33 int[] arr = {12, 11, 13, 5, 6, 7};34 System.out.println("Before: " + Arrays.toString(arr));35 heapSort(arr);36 System.out.println("After: " + Arrays.toString(arr));37 }38}Código de Heap Sort en C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11 while (true) {12 int largest = i, l = 2 * i + 1, r = 2 * i + 2;13 if (l < n && a[l] > a[largest]) largest = l;14 if (r < n && a[r] > a[largest]) largest = r;15 if (largest == i) return;16 std::swap(a[i], a[largest]);17 i = largest;18 }19}20
21void heapSort(std::vector<int>& a) {22 int n = static_cast<int>(a.size());23 // Build a max-heap in place24 for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25 // Repeatedly move the max to the end and shrink the heap26 for (int end = n - 1; end > 0; --end) {27 std::swap(a[0], a[end]);28 siftDown(a, end, 0);29 }30}31
32int main() {33 std::vector<int> data = {12, 11, 13, 5, 6, 7};34 std::cout << "Before: ";35 printVec(data);36 heapSort(data);37 std::cout << "After: ";38 printVec(data);39 return 0;40}Código de Heap Sort en C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void siftDown(int a[], int n, int i) {9 while (1) {10 int largest = i, l = 2 * i + 1, r = 2 * i + 2;11 if (l < n && a[l] > a[largest]) largest = l;12 if (r < n && a[r] > a[largest]) largest = r;13 if (largest == i) return;14 int tmp = a[i];15 a[i] = a[largest];16 a[largest] = tmp;17 i = largest;18 }19}20
21void heapSort(int a[], int n) {22 // Build a max-heap in place23 for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24 // Repeatedly move the max to the end and shrink the heap25 for (int end = n - 1; end > 0; end--) {26 int tmp = a[0];27 a[0] = a[end];28 a[end] = tmp;29 siftDown(a, end, 0);30 }31}32
33int main(void) {34 int data[] = {12, 11, 13, 5, 6, 7};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 heapSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}Preguntas frecuentes sobre Heap Sort
¿Cuál es la complejidad temporal de heap sort?
Heap sort es
O(n log n) en el mejor, el promedio y el peor caso. Construir el heap es O(n) y cada una de las n extracciones cuesta O(log n). Usa O(1) de espacio adicional.¿Es estable heap sort?
No. La operación de hundimiento puede mover elementos iguales unos sobre otros, por lo que heap sort no preserva el orden relativo de las claves iguales.
¿Cuándo debería usar heap sort?
Usa heap sort cuando necesites un peor caso garantizado de
O(n log n) con solo O(1) de memoria adicional. Evita el riesgo de O(n²) de quicksort sin el búfer de O(n) de merge sort, a costa de la estabilidad y el rendimiento de caché.¿Cuál es la diferencia entre heap sort y quicksort?
Ambos ordenan en el sitio, pero quicksort tiene un peor caso de
O(n²) mientras que heap sort garantiza O(n log n). En la práctica quicksort suele ser más rápido por su mejor localidad de caché y menos intercambios, así que heap sort se prefiere sobre todo cuando la cota del peor caso debe estar garantizada.¿Cómo se relaciona heap sort con una cola de prioridad?
Un heap binario es la implementación estándar de una cola de prioridad, y heap sort consiste esencialmente en extraer repetidamente el máximo de esa cola. Si ya mantienes tus datos en un heap, extraer los elementos uno a uno te da el orden ordenado gratis.
¿Heap sort necesita un max-heap o un min-heap?
Para ordenar de forma ascendente en el sitio, usa un max-heap: el elemento más grande se intercambia al final en cada pasada, haciendo crecer la cola ordenada desde la derecha. Un min-heap produciría orden descendente en el sitio, u orden ascendente si extraes hacia un arreglo separado.
Recursos relacionados
Más visualizaciones
