Heap (montículo binario)
Última actualización
Un montículo binario es un árbol binario completo que mantiene el valor más pequeño (min-heap) o más grande (max-heap) en la raíz. Esta visualización es un min-heap: cada padre es menor o igual que sus hijos. Para añadir un valor lo agregas en la siguiente posición libre y luego lo "haces subir", intercambiándolo con su padre mientras sea menor, hasta que se cumpla de nuevo la propiedad de montículo. Pulsa reproducir arriba para ver cómo cada nuevo valor sube hasta su lugar.
Como un montículo es un árbol completo, se almacena de forma compacta en un arreglo: los hijos del nodo i están en 2i+1 y 2i+2. Insertar y quitar el mínimo son O(log n) (un camino de la raíz a una hoja), mientras que consultar el mínimo es O(1), que es justo lo que necesita una cola de prioridad.
Complejidad temporal y espacial
| Operación | Complejidad | Notas |
|---|---|---|
| Consultar mín/máx | O(1) | Siempre es la raíz |
| Insertar (push) | O(log n) | Subir por un camino |
| Quitar mín/máx | O(log n) | Bajar por un camino |
| Construir el montículo | O(n) | Heapify de una vez |
| Espacio | O(n) | Basado en arreglo, sin punteros |
Paso a paso (push)
| Paso | Qué ocurre |
|---|---|
| 1 | Agrega el nuevo valor al final (la siguiente hoja libre). |
| 2 | Compáralo con su padre. |
| 3 | Si es menor (min-heap), intercámbialo hacia arriba. |
| 4 | Repite hasta que ya no sea menor que su padre o llegue a la raíz. |
Ejemplo resuelto
Construyendo un min-heap insertando [5, 3, 8, 1, 4] un valor a la vez:
| Push | Arreglo tras subir | Acción |
|---|---|---|
5 | [5] | El primer valor pasa a ser la raíz. |
3 | [3, 5] | 3 < padre 5, así que sube hasta la raíz. |
8 | [3, 5, 8] | 8 > padre 5, así que se queda como hoja. |
1 | [1, 3, 8, 5] | 1 < padre 5, intercambia; luego 1 < padre 3, sube hasta la raíz. |
4 | [1, 3, 8, 5, 4] | 4 > padre 3, así que se queda; el mínimo 1 sigue en la raíz. |
Cuándo usar un heap
| Úsalo cuando | Evítalo cuando |
|---|---|
| Necesitas repetidamente el elemento más pequeño o más grande de un conjunto cambiante. | Necesitas buscar valores arbitrarios, no solo el extremo: usa un BST o un conjunto hash. |
| Implementas una cola de prioridad para Dijkstra, A* o un planificador. | Necesitas mantener los datos totalmente ordenados en todo momento. |
Quieres inserción y extracción del mínimo en O(log n) con un arreglo compacto. | Necesitas búsqueda o eliminación rápida de un elemento concreto (no la raíz). |
| Necesitas fusionar un flujo de elementos y extraerlos por prioridad. | El conjunto de datos es diminuto y un recorrido lineal es más simple y suficientemente rápido. |
Código de Heap (Priority Queue)
Una implementación limpia y ejecutable de Heap (Priority Queue) 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 (Priority Queue) en Python
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])Código de Heap (Priority Queue) en JavaScript
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Código de Heap (Priority Queue) en Java
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}Código de Heap (Priority Queue) en C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}Código de Heap (Priority Queue) en C
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}Preguntas frecuentes sobre heaps
¿Para qué se usa un heap?
Los heaps implementan colas de prioridad, que impulsan el algoritmo de camino más corto de Dijkstra, los planificadores de tareas y las simulaciones de eventos. También son el motor detrás de heapsort. Siempre que necesites repetidamente el elemento más pequeño o más grande de un conjunto cambiante, un heap es la herramienta.
¿Cuál es la diferencia entre un heap y un árbol binario de búsqueda?
Ambos son árboles binarios, pero un BST mantiene un orden completo de izquierda a derecha (permitiendo búsqueda ordenada), mientras que un heap solo garantiza la relación padre-hijo (mínimo o máximo en la raíz). Un heap da acceso O(1) al valor extremo; un BST da búsqueda O(log n) de cualquier valor.
¿Por qué se almacena un heap en un arreglo?
Como un heap siempre es un árbol binario completo, sus nodos se mapean perfectamente a índices de arreglo: los hijos del índice
i están en 2i+1 y 2i+2, y el padre en (i-1)/2. Esto evita almacenar punteros a los hijos y ofrece un excelente rendimiento de caché.¿Es un heap lo mismo que un arreglo ordenado?
No. Un heap solo garantiza que cada padre sea menor (min-heap) o mayor (max-heap) que sus hijos, así que los hermanos y primos no tienen ningún orden particular. Un arreglo ordenado está totalmente ordenado pero cuesta
O(n) insertar en él, mientras que un heap inserta en O(log n) y sigue dando acceso instantáneo al valor extremo.¿Cuándo debería usar un heap en vez de simplemente ordenar un arreglo?
Recurre a un heap cuando los datos cambian constantemente y solo necesitas el mínimo o el máximo actual: insertar y extraer cuestan
O(log n) cada uno, frente a reordenar todo el arreglo. Si tienes un conjunto de datos estático y quieres todos los elementos en orden, una sola ordenación O(n log n) es más simple y a menudo más rápida.¿Construir un heap con n elementos cuesta O(n log n)?
No si lo construyes de una sola vez. Insertar
n elementos uno por uno es O(n log n), pero el heapify de abajo hacia arriba, que baja desde el último padre hasta la raíz, se ejecuta en O(n) en total, porque la mayoría de los nodos están cerca del fondo y bajan solo una distancia corta.Recursos relacionados
Más visualizaciones
