Montículo y ordenamiento por montículo
En resumen: Un montículo (heap) es un árbol binario casi completo guardado en un arreglo, con el elemento mayor (o menor) siempre en la raíz; el ordenamiento por montículo ordena en el sitio en O(n log n).
Problema
Los 10 primeros de un millón
La tienda tiene un millón de productos y sabe cuántas veces se vendió cada uno. La página de inicio necesita los 10 primeros por ventas. Esto se calcula cada vez que se abre la página.
Lo primero que viene a la mente es ordenarlos todos y tomar los primeros 10. El ordenamiento por mezcla hace unos 18,7 millones de comparaciones con un millón de productos (mira el ordenamiento por mezcla). Necesitas 10 filas de eso. Los otros 999 990 productos se ordenan para nada.
Hay también un segundo problema. El quicksort ordena en el sitio, pero con un mal pivote cae a O(n²) (mira el quicksort). El ordenamiento por mezcla es O(n log n) siempre, pero necesita un segundo arreglo tan grande como el primero. ¿Se puede tener las dos cosas: en el sitio y O(n log n) siempre?
La idea
Un montículo: un árbol guardado en un arreglo
Para ambas hace falta una estructura que sepa una sola cosa: cuál es el mayor. No hace falta ordenarlo todo.
Dibuja el arreglo como un árbol. El índice 0 es la cima. Bajo cada índice i hay dos hijos:
- el hijo izquierdo está en 2i + 1;
- el hijo derecho está en 2i + 2;
- el padre del índice i está en (i - 1) / 2, con división entera.
No hay punteros. El árbol es solo una forma de mirar el arreglo.
El arreglo es un montículo (un montículo máximo, para ser precisos) cuando cada padre es al menos tan grande como sus hijos. Entonces el mayor siempre está en el índice 0. Ese es el único orden que hay: los hermanos pueden estar en cualquier orden entre sí.
Míralo
Los hijos y el padre por índice
Un montículo de siete ventas. El programa recorre los padres e imprime sus hijos, y luego encuentra el padre del índice 4:
int[] heap = {58, 40, 25, 31, 12, 3, 7};for (int i = 0; 2 * i + 2 < heap.length; i++) { int left = 2 * i + 1, right = 2 * i + 2; System.out.println(heap[i] + " -> " + heap[left] + " " + heap[right]);}int child = 4;int parent = (child - 1) / 2;System.out.println("el padre de " + heap[child] + " (índice " + child + ") es " + heap[parent] + " (índice " + parent + ")");58 -> 40 2540 -> 31 1225 -> 3 7el padre de 12 (índice 4) es 40 (índice 1)58 está sobre 40 y 25, 40 sobre 31 y 12, 25 sobre 3 y 7. Cada padre es mayor que sus hijos, y 58 es el mayor.
(child - 1) / 2 es una división de enteros: 3 / 2 es 1, el resto se descarta.Míralo
Hundir: cómo un arreglo se convierte en montículo
¿Cómo se convierte en montículo un arreglo en cualquier orden? Con una operación: hundir (sift down). El elemento en el índice i se compara con sus dos hijos. Si alguno es mayor, intercambia su lugar con el mayor, y el elemento sigue bajando. Se detiene cuando es al menos tan grande como sus hijos o cuando no hay hijos.
La construcción ejecuta el hundimiento para cada padre, desde el último hasta la cima. Las hojas (la fila de abajo) no tienen hijos: cada una de ellas es un montículo por sí sola. Así que cuando llegas a un padre, los dos subárboles bajo él ya son montículos, y solo tiene que hundirse hasta su lugar.
static void siftDown(int[] a, int i, int n) { while (true) { int big = i; int left = 2 * i + 1, right = 2 * i + 2; if (left < n && a[left] > a[big]) big = left; if (right < n && a[right] > a[big]) big = right; if (big == i) return; swap(a, i, big); i = big; }}El ordenamiento por montículo es la construcción más un bucle más. El máximo está en el índice 0: se intercambia con el último elemento y ya está en su lugar definitivo. El montículo se reduce en uno, y la nueva cima se hunde. Eso ocurre n - 1 veces:
static void buildHeap(int[] a) { for (int i = a.length / 2 - 1; i >= 0; i--) { siftDown(a, i, a.length); }}
static void heapSort(int[] a) { buildHeap(a); for (int end = a.length - 1; end > 0; end--) { swap(a, 0, end); siftDown(a, 0, end); }}int[] sales = {12, 40, 7, 31, 58, 3, 25};buildHeap(sales);System.out.println("Montículo: " + Arrays.toString(sales));heapSort(sales);System.out.println("Ordenado: " + Arrays.toString(sales));Montículo: [58, 40, 25, 31, 12, 3, 7]Ordenado: [3, 7, 12, 25, 31, 40, 58]static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp;}
static void siftDown(int[] a, int i, int n) { while (true) { int big = i; int left = 2 * i + 1, right = 2 * i + 2; if (left < n && a[left] > a[big]) big = left; if (right < n && a[right] > a[big]) big = right; if (big == i) return; swap(a, i, big); i = big; }}
static void buildHeap(int[] a) { for (int i = a.length / 2 - 1; i >= 0; i--) { siftDown(a, i, a.length); }}
static void heapSort(int[] a) { buildHeap(a); for (int end = a.length - 1; end > 0; end--) { swap(a, 0, end); siftDown(a, 0, end); }}Paso a paso, en palabras
- Siete ventas en un arreglo. El mismo arreglo es un árbol: los hijos del índice i están en 2i + 1 y 2i + 2.
- La construcción empieza por el último padre, índice 2. siftDown: 7 es menor que su hijo 25, así que se intercambian.
- Índice 1: 40 contra 31 y 58. El hijo mayor es 58: intercambio.
- La raíz: 12 se intercambia con 58 y sigue hundiéndose. Un nivel más abajo 40 es mayor: un intercambio más.
- Un montículo: cada padre es al menos tan grande como sus hijos. El máximo, 58, está en el índice 0.
- Ordenamiento por montículo: el máximo se intercambia con el último elemento. 58 está en su lugar definitivo, y el montículo se reduce a seis.
- La nueva cima, 7, se hunde: intercambio con 40, luego con 31. Ahora arriba está 40, el siguiente máximo. Eso se repite n - 1 veces.
No hay un segundo arreglo: los intercambios ocurren en el propio arreglo. Eso es ordenar en el sitio.
Pruébalo
Predice la salida
La construcción ejecuta el hundimiento desde el último padre hasta la cima. ¿Qué hay en el arreglo después?
int[] sales = {5, 9, 2, 8};buildHeap(sales);System.out.println(Arrays.toString(sales));Pruébalo
Completa
El hijo izquierdo del índice i es:
int left = , right = 2 * i + 2;Los hijos de i están en 2i + 1 y 2i + 2. La cima está en 0, así que sus hijos están en 1 y 2, no en 0 y 1.
La idea
Cuánto cuesta
- Hundir: en cada nivel dos comparaciones y como máximo un intercambio. Un árbol de n elementos tiene unos log₂ n niveles, así que hundir es O(log n).
- Construir: parece n hundimientos de log n cada uno, pero es O(n). La mitad de los elementos son hojas y no se hunden en absoluto, un cuarto baja como mucho un nivel, un octavo dos… La suma es menor que 2n.
- Ordenamiento por montículo: la construcción más n - 1 hundimientos desde la cima: O(n log n) en todos los casos. No hay entrada mala, como un mal pivote en el quicksort.
Ejecútalo contra el ordenamiento por mezcla. Los dos cuentan sus comparaciones:
- Ordenamiento por montículo
O(n log n) - Ordenar (merge sort)
O(n log n)
| Algoritmo | n = 10 | n = 1000 | n = 100.000 |
|---|---|---|---|
| Ordenamiento por montículo | 38 | 16.807 | 3.019.656 |
| Ordenar (merge sort) | 21 | 8709 | 1.536.371 |
static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp;}
static void siftDown(int[] a, int i, int n) { while (true) { int big = i; int left = 2 * i + 1, right = 2 * i + 2; if (left < n && a[left] > a[big]) big = left; if (right < n && a[right] > a[big]) big = right; if (big == i) return; swap(a, i, big); i = big; }}
static void buildHeap(int[] a) { for (int i = a.length / 2 - 1; i >= 0; i--) { siftDown(a, i, a.length); }}
static void heapSort(int[] a) { buildHeap(a); for (int end = a.length - 1; end > 0; end--) { swap(a, 0, end); siftDown(a, 0, end); }}Las dos curvas crecen igual, pero el ordenamiento por montículo hace casi el doble de comparaciones: para 100 000 ventas, 3 019 656 contra 1 536 371. Cada hundimiento desde la cima llega casi hasta abajo, porque allí se puso un elemento pequeño.
Hay una segunda cosa que el conteo no muestra: la memoria. Desde el índice i el hundimiento salta a 2i + 1. En un arreglo grande eso está lejos, y cada vez el procesador espera a que llegue otro trozo de memoria. El ordenamiento por mezcla y el quicksort leen en orden, y justo entonces el procesador es rápido. Así que en la práctica el ordenamiento por montículo es más lento, aunque promete O(n log n) siempre.
Más precisamente, para curiosos
¿Por qué el sort incorporado no es un ordenamiento por montículo? Por lo anterior. Es la alternativa de reserva: en C# Array.Sort es introsort, que empieza con quicksort y cambia a ordenamiento por montículo si la partición se hace demasiado profunda. Así conserva O(n log n) sin pagar el precio del ordenamiento por montículo cada vez. Tampoco es estable: dos productos con las mismas ventas pueden intercambiar su orden. Qué significa eso está en la lección sobre estabilidad.
Por qué construir es O(n): a la altura h desde abajo hay unos n / 2ʰ⁺¹ elementos, y cada uno baja como mucho h niveles. La suma n · (1/4 + 2/8 + 3/16 + …) es n · 1 = n.
Pruébalo
Encuentra el error
Alguien escribió el ordenamiento por montículo, pero el resultado ordenado sale revuelto:
static void heapSort(int[] a) { buildHeap(a); for (int end = a.length - 1; end > 0; end--) { swap(a, 0, end); siftDown(a, 0, a.length); }}int[] sales = {12, 40, 7, 31, 58, 3, 25};heapSort(sales);System.out.println(Arrays.toString(sales));[58, 31, 40, 25, 12, 7, 3]¿En qué línea está el error?
Elige la línea con el error.
El hundimiento recibe todo el arreglo, no solo el montículo. El máximo puesto al final vuelve a ser un «hijo» y sube otra vez. El límite es end: todo desde end ya está ordenado, y el hundimiento no debe verlo. Con end la salida es [3, 7, 12, 25, 31, 40, 58].
Míralo
Los 10 primeros sin ordenarlo todo
De vuelta a la página de inicio. Da la vuelta a la idea: mantén un montículo mínimo de 10 elementos, con el menor de ellos en la cima. Es el «décimo»: la barra que un producto tiene que superar para entrar.
- Mientras haya menos de 10, todo producto entra.
- Después, cada nuevo se compara solo con la cima. Si es mayor, toma el lugar de la cima y se hunde. Si no, queda fuera tras una comparación.
PriorityQueue es justo un montículo mínimo así: peek() da la cima, poll() la saca, add() añade y sube.record Product(int id, int sold) {}
PriorityQueue<Product> best = new PriorityQueue<>(Comparator.comparingInt(Product::sold));for (int id = 1; id <= 1_000_000; id++) { Product p = new Product(id, (int) (id * 48271L % 1_000_003)); if (best.size() < 10) { best.add(p); } else if (p.sold() > best.peek().sold()) { best.poll(); best.add(p); }}List<Product> top = new ArrayList<>(best);top.sort(Comparator.comparingInt(Product::sold).reversed());for (Product p : top) { System.out.println("producto " + p.id() + ": " + p.sold() + " vendidos");}producto 188706: 1000002 vendidosproducto 377412: 1000001 vendidosproducto 566118: 1000000 vendidosproducto 754824: 999999 vendidosproducto 943530: 999998 vendidosproducto 132233: 999997 vendidosproducto 320939: 999996 vendidosproducto 509645: 999995 vendidosproducto 698351: 999994 vendidosproducto 887057: 999993 vendidosEjecútalo contra ordenarlo todo, hasta un millón:
- El top 10 con un montículo
O(n) - Ordenar (merge sort)
O(n log n)
| Algoritmo | n = 10 | n = 1000 | n = 100.000 | n = 1.000.000 |
|---|---|---|---|---|
| El top 10 con un montículo | 15 | 1177 | 100.410 | 1.000.467 |
| Ordenar (merge sort) | 21 | 8709 | 1.536.371 | 18.674.993 |
Con un millón de productos el montículo hace 1 000 467 comparaciones, y el ordenamiento por mezcla 18 674 993. El trabajo es O(n · log 10): el montículo nunca pasa de 10, así que hay casi exactamente una comparación por producto.
Más precisamente, para curiosos
Un montículo del que sacas «lo más importante» y al que añades nuevos es una cola de prioridad. Es un tema aparte en el módulo «Estructuras de datos»: allí está la subida, y por qué las tareas de un planificador, los eventos de una simulación y Dijkstra se apoyan en ella.
PriorityQueue en Java es un montículo mínimo por orden natural. Para un montículo máximo pasas Comparator.reverseOrder().Cómo es en los otros lenguajes: Java tiene PriorityQueue, C# PriorityQueue<TElement, TPriority>, Python heapq, y JavaScript no tiene un montículo incorporado.
Ejercicio
Los tres primeros
Resuelve la tarea en tu editor.
Los tres primeros por ventas. Las ventas de doce productos son 12, 40, 7, 31, 58, 3, 25, 44, 19, 36, 50, 8. Encuentra los tres mayores con un montículo mínimo que nunca tenga más de tres elementos, e imprímelos empezando por el mayor.
Los tres primeros: [58, 50, 44]Más tareas
- Un montículo mínimo a mano. Reescribe
siftDownpara que un padre sea como mucho tan grande como sus hijos. Ordena con él las ventas en orden inverso. - Contar las comparaciones. Añade un contador al hundimiento y ejecuta el ordenamiento por montículo con 7, 1000 y 100 000 ventas. ¿Crece como n log n?
- Los 10 últimos. ¿Qué 10 productos se venden peor? ¿Qué tipo de montículo necesitas ahora?
Test