Recorrido narrado · El heap: un árbol dentro de un array

Heap no es árbol de búsqueda

Heap y BST son árboles binarios con un invariante de orden, y se confunden a menudo. Son muy distintos:

Los dos árboles de abajo tienen los mismos siete valores. Mira por dónde tiene que pasar la búsqueda del 7 en cada uno.

BST: buscar el 7 sigue un camino (5, 8, 7). A cada paso, el invariante dice a qué lado ir.

Min-heap con los mismos valores. Buscar el 7: el invariante no dice en qué rama está, así que hay que mirar las dos.

	BST	Min-heap
invariante	izquierda menor, derecha mayor	padre menor o igual que los hijos
responde rápido	buscar cualquier clave, rangos, en orden	el mínimo
buscar una clave cualquiera	O(h)	O(n): puede estar en cualquier rama
forma	depende de las inserciones	siempre completo: altura log₂ n
memoria	nodos con punteros	un array

El heap promete menos y por eso es más simple: siempre está balanceado, sin rotaciones, y vive en un array contiguo. La interfaz que cumple se llama cola de prioridad.

Su fila en la tabla de costos

Cada estructura nueva ocupa una fila en la tabla de costos de la ruta. Esta es la parte de la fila del heap que ya conoces, junto a un array ordenado:

Representación	`mínimo`	buscar una clave cualquiera
heap binario (min-heap)	O(1)	O(n): puede estar en cualquier rama
array ordenado	O(1), si el mínimo va al final	O(log n), con búsqueda binaria

El heap tiene el mínimo a la vista pero no sabe buscar. Lo que cuesta insertar y extraer llega en el tema siguiente.