Heap
MediaNo Prioritaria
Estructura de árbol especializada que cumple la propiedad de heap.
¿Qué es un Heap?
Un Heap es un árbol binario completo donde cada nodo cumple una propiedad de orden:
- Max Heap: cada nodo es mayor o igual a sus hijos.
- Min Heap: cada nodo es menor o igual a sus hijos.
Se utiliza comúnmente para implementar estructuras como colas de prioridad.
Analogía del Mundo Real
Imagina una fila para entrar a un evento donde quienes tienen un boleto VIP siempre pasan primero. Un Heap actúa igual: los elementos con más prioridad se colocan arriba y son atendidos primero.
Cómo Funciona Internamente un Heap
- Se representa comúnmente como un array.
- El nodo padre de índice i tiene:
- Hijo izquierdo en 2i + 1
- Hijo derecho en 2i + 2
- Al insertar un nuevo elemento, se ubica al final y luego se reordena con 'heapify up'.
- Al eliminar, se toma el tope y se reemplaza por el último, luego se reordena con 'heapify down'.
Ejemplos de Código
// Min Heap implementation in JavaScript
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(i) {
return Math.floor((i - 1) / 2);
}
getLeftChildIndex(i) {
return 2 * i + 1;
}
getRightChildIndex(i) {
return 2 * i + 2;
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
insert(value) {
this.heap.push(value);
this.heapifyUp();
}
heapifyUp() {
let index = this.heap.length - 1;
while (index > 0) {
let parentIndex = this.getParentIndex(index);
if (this.heap[index] < this.heap[parentIndex]) {
this.swap(index, parentIndex);
index = parentIndex;
} else {
break;
}
}
}
extractMin() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown();
return min;
}
heapifyDown() {
let index = 0;
const length = this.heap.length;
while (this.getLeftChildIndex(index) < length) {
let smallerChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
if (
rightChildIndex < length &&
this.heap[rightChildIndex] < this.heap[smallerChildIndex]
) {
smallerChildIndex = rightChildIndex;
}
if (this.heap[index] > this.heap[smallerChildIndex]) {
this.swap(index, smallerChildIndex);
index = smallerChildIndex;
} else {
break;
}
}
}
}Explicación Visual (🚧 En progreso)
Pronto disponible
Estamos trabajando en un video para explicar esta estructura de datos
Complejidad en Tiempo y Espacio
| Operación | Promedio | Peor Escenario |
|---|---|---|
| Acceso | O(1) | O(1) |
| Búsqueda | O(n) | O(n) |
| Inserción | O(log n) | O(log n) |
| Eliminación | O(log n) | O(log n) |
Donde n es el número de elementos en el heap.
La operación de acceso retorna el elemento raíz (mínimo o máximo). Buscar un valor arbitrario requiere recorrer el heap completo.
Operaciones Comunes
- insert(value)Agrega un valor al heap manteniendo la propiedad
- extractMin()Retorna y elimina el valor mínimo (Min Heap)
- peek()Devuelve el valor en la raíz sin eliminarlo
Practica
Aplica lo que has aprendido