Heap: cuando la prioridad manda

Lic. Carlos Enrique Loria Beeche.

Séptimo artículo técnico de la saga “Estructuras de datos: cuando la memoria se convierte en inteligencia”

Este artículo forma parte de la saga que inicié con Estructuras de datos: cuando la memoria se convierte en inteligencia, donde presenté las ocho estructuras de datos fundamentales que iremos recorriendo paso a paso.

En las entregas anteriores estudiamos el array, el estacionamiento numerado de la memoria, la linked list, la búsqueda del tesoro en la memoria, la stack, la pila y el recuerdo del último paso, la queue, la cola y la justicia del turno, la hash table, encontrar sin buscar, y el binary search tree, ordenar para encontrar mejor.

Ahora vamos a estudiar una estructura que se parece a un árbol, pero que no busca ordenar todos los elementos de manera completa. Su objetivo es más práctico: mantener siempre disponible el elemento de mayor o menor prioridad.

Se trata del heap.

Un heap nos enseña que no siempre importa tener todo perfectamente ordenado; a veces basta con saber cuál es lo más urgente, lo más grande, lo más pequeño o lo más importante.

¿Qué es un heap?

Un heap es una estructura de datos basada en prioridades. Aunque suele representarse como un árbol binario, su propósito principal no es permitir búsquedas generales como un árbol binario de búsqueda.

La idea central de un heap es mantener en la raíz el elemento más importante según una regla de prioridad.

En un max-heap, el valor mayor queda en la raíz.

En un min-heap, el valor menor queda en la raíz.

Por ejemplo, un max-heap podría verse así:

          100
        /     \
      80       60
     /  \     /  \
   50   70   40   30

El valor más grande, 100, está en la raíz. Los hijos de cada nodo no son mayores que su padre. Esa es la regla fundamental del max-heap.

La regla del heap

En un heap no necesitamos que todo el árbol esté perfectamente ordenado. Lo que necesitamos es que se cumpla una regla local entre padres e hijos.

Max-heap

En un max-heap, cada nodo padre debe ser mayor o igual que sus hijos.

Padre >= hijos

Eso garantiza que el valor máximo esté siempre en la raíz.

          100
        /     \
      80       60

Aquí, 100 es mayor que 80 y 60, por lo tanto respeta la regla.

Min-heap

En un min-heap, cada nodo padre debe ser menor o igual que sus hijos.

Padre <= hijos

Eso garantiza que el valor mínimo esté siempre en la raíz.

          10
        /    \
      20      30

Aquí, 10 es menor que 20 y 30, por lo tanto el menor valor queda arriba.

El heap no ordena todo; asegura que la prioridad principal esté siempre arriba.

Heap no es lo mismo que Binary Search Tree

Como ambos se dibujan como árboles, es fácil confundir un heap con un binary search tree. Pero son estructuras distintas.

Estructura	Regla principal	Objetivo
Binary Search Tree	Menores a la izquierda, mayores a la derecha	Buscar comparando y mantener orden
Heap	El padre tiene mayor o menor prioridad que sus hijos	Acceder rápido al elemento prioritario

En un árbol binario de búsqueda, los valores se organizan para facilitar búsquedas. En un heap, los valores se organizan para que el elemento prioritario esté arriba.

Por eso, en un heap no podemos asumir que todo lo que está a la izquierda es menor y todo lo que está a la derecha es mayor. Esa regla pertenece al árbol binario de búsqueda, no al heap.

La analogía de la sala de urgencias

Una buena analogía para entender un heap es una sala de urgencias.

En una fila común, como vimos al estudiar la queue, el primero que llega es el primero que se atiende.

Pero en una sala de urgencias, la atención no depende solamente del orden de llegada. Depende de la prioridad médica.

Una persona con un caso grave puede ser atendida antes que otra que llegó primero, pero tiene una condición menos urgente.

Eso es lo que hace un heap cuando se usa para implementar una cola de prioridad: mantiene disponible el elemento que debe ser atendido primero según su prioridad.

La cola respeta el turno; el heap respeta la prioridad.

Representación interna de un heap

Aunque solemos dibujar el heap como un árbol, muchas implementaciones lo guardan internamente en un array.

Por ejemplo, este heap:

          100
        /     \
      80       60
     /  \     /  \
   50   70   40   30

Puede representarse en un array así:

Índice:  0    1   2   3   4   5   6
Valor: 100   80  60  50  70  40  30

La relación entre padres e hijos se calcula mediante índices.

Si usamos índices iniciando en cero:

hijo izquierdo = 2 * índice + 1
hijo derecho   = 2 * índice + 2
padre          = (índice - 1) / 2

Esto permite representar el árbol sin necesidad de crear nodos enlazados con punteros o referencias.

Insertar en un heap

Cuando insertamos un nuevo elemento en un heap, normalmente se coloca al final y luego se reacomoda hacia arriba hasta que se cumpla nuevamente la regla del heap.

Supongamos este max-heap:

          100
        /     \
      80       60
     /  \     /  \
   50   70   40   30

Si insertamos 90, primero lo colocamos al final:

          100
        /     \
      80       60
     /  \     /  \
   50   70   40   30
  /
90

Pero 90 es mayor que su padre 50, así que debe subir.

          100
        /     \
      80       60
     /  \     /  \
   90   70   40   30
  /
50

Ahora 90 también es mayor que 80, así que vuelve a subir:

          100
        /     \
      90       60
     /  \     /  \
   80   70   40   30
  /
50

El proceso termina cuando la regla del max-heap se cumple nuevamente.

Este reacomodo hacia arriba suele llamarse heapify up o sift up.

Extraer la raíz

La operación más importante de un heap es extraer el elemento prioritario.

En un max-heap, esto significa extraer el valor máximo. En un min-heap, extraer el valor mínimo.

Supongamos este max-heap:

          100
        /     \
      90       60
     /  \     /  \
   80   70   40   30

El valor prioritario es 100, porque está en la raíz.

Al extraerlo, tomamos el último elemento del heap y lo colocamos temporalmente en la raíz:

          30
        /     \
      90       60
     /  \     /
   80   70   40

Ahora el heap está desordenado, porque 30 no debería estar arriba. Entonces lo bajamos intercambiándolo con el hijo de mayor prioridad.

          90
        /     \
      30       60
     /  \     /
   80   70   40

Luego comparamos 30 con sus hijos y lo seguimos bajando:

          90
        /     \
      80       60
     /  \     /
   30   70   40

Y finalmente:

          90
        /     \
      80       60
     /  \     /
   30   70   40

Si todavía se necesitara reacomodar, el proceso continuaría. Esta operación se conoce como heapify down o sift down.

Operaciones básicas de un heap

Operación	Descripción	Costo típico
consultar raíz	Ver el elemento de mayor o menor prioridad	O(1)
insertar	Agregar un elemento y reacomodarlo	O(log n)
extraer raíz	Retirar el elemento prioritario y reordenar	O(log n)
construir heap	Convertir una colección en heap	O(n)
recorrer	Visitar todos los elementos	O(n)

La raíz puede consultarse en tiempo constante porque siempre está en la primera posición. Insertar y extraer requieren reacomodar el árbol, por eso su costo típico es O(log n).

Ejemplo en C++

En C++, podemos usar priority_queue, que por defecto se comporta como un max-heap.

#include &lt;iostream&gt;
#include &lt;queue&gt;
using namespace std;

int main() {
    priority_queue&lt;int&gt; heap;

    heap.push(50);
    heap.push(100);
    heap.push(30);
    heap.push(80);
    heap.push(60);

    cout &lt;&lt; "Elemento de mayor prioridad: "
         &lt;&lt; heap.top() &lt;&lt; endl;

    heap.pop();

    cout &lt;&lt; "Después de extraer, nuevo tope: "
         &lt;&lt; heap.top() &lt;&lt; endl;

    cout &lt;&lt; "Extrayendo todos los elementos:" &lt;&lt; endl;

    while (!heap.empty()) {
        cout &lt;&lt; heap.top() &lt;&lt; endl;
        heap.pop();
    }

    return 0;
}

En este ejemplo, el mayor valor aparece siempre en el tope. Por eso priority_queue es útil cuando necesitamos atender primero el elemento de mayor prioridad.

Ejemplo en C#

En C#, podemos usar PriorityQueue<TElement, TPriority>. En esta estructura, el elemento con menor prioridad numérica sale primero. Es decir, se comporta como un min-heap por prioridad.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        PriorityQueue&lt;string, int&gt; cola = new PriorityQueue&lt;string, int&gt;();

        cola.Enqueue("Caso leve", 3);
        cola.Enqueue("Caso crítico", 1);
        cola.Enqueue("Caso moderado", 2);

        Console.WriteLine("Atendiendo por prioridad:");

        while (cola.Count &gt; 0)
        {
            string caso = cola.Dequeue();
            Console.WriteLine(caso);
        }
    }
}

En este ejemplo, "Caso crítico" tiene prioridad 1, por eso sale antes que los demás. Luego sale el caso moderado y finalmente el caso leve.

Ejemplo en Python

En Python, el módulo heapq permite trabajar con heaps. Por defecto implementa un min-heap.

import heapq

heap = []

heapq.heappush(heap, 50)
heapq.heappush(heap, 100)
heapq.heappush(heap, 30)
heapq.heappush(heap, 80)
heapq.heappush(heap, 60)

print("Elemento de menor prioridad numérica:", heap[0])

print("Extrayendo elementos:")

while heap:
    print(heapq.heappop(heap))

El resultado sale en orden ascendente porque heapq mantiene el menor elemento en la raíz.

Si quisiéramos simular un max-heap en Python, podríamos insertar los valores negativos:

import heapq

heap = []

for valor in [50, 100, 30, 80, 60]:
    heapq.heappush(heap, -valor)

print("Extrayendo como max-heap:")

while heap:
    print(-heapq.heappop(heap))

Al usar valores negativos, el menor número interno representa el mayor valor original.

¿Cuándo conviene usar un heap?

Un heap conviene cuando necesitamos acceder repetidamente al elemento de mayor o menor prioridad.

Algunos casos típicos son:

Colas de prioridad.
Sistemas de atención por urgencia.
Planificación de tareas.
Algoritmos de rutas.
Selección de los mayores o menores elementos.
Algoritmos de ordenamiento como heapsort.
Simulaciones de eventos.
Procesamiento de trabajos pendientes según prioridad.

El heap es especialmente útil cuando no necesitamos tener todo ordenado, sino encontrar rápidamente el elemento más prioritario.

Comparación con queue

La cola tradicional y el heap pueden parecer relacionados porque ambos ayudan a decidir qué elemento sale primero. Pero el criterio es distinto.

Estructura	Criterio de salida	Ejemplo
Queue	Sale primero quien llegó primero	Fila de banco
Heap	Sale primero quien tiene mayor prioridad	Sala de urgencias

La cola respeta el orden de llegada. El heap respeta el orden de prioridad.

Comparación con binary search tree

El heap y el árbol binario de búsqueda también se diferencian claramente.

Estructura	Organización	Fortaleza
Binary Search Tree	Menores a la izquierda, mayores a la derecha	Buscar y recorrer en orden
Heap	Padres con prioridad sobre hijos	Extraer rápido el elemento prioritario

El árbol binario de búsqueda sirve para buscar comparando. El heap sirve para priorizar.

Aplicación clásica: cola de prioridad

La aplicación más natural del heap es la cola de prioridad.

En una cola de prioridad, cada elemento tiene una prioridad asociada. Al extraer un elemento, no sale necesariamente el primero que llegó, sino el más importante según la prioridad.

Por ejemplo:

Elemento             Prioridad
Caso crítico         1
Caso moderado        2
Caso leve            3

Si una prioridad menor significa mayor urgencia, el caso crítico debe salir primero.

Este patrón aparece en sistemas operativos, planificación de procesos, redes, simulaciones, videojuegos, algoritmos de rutas y administración de tareas.

La cola de prioridad es una cola donde el turno lo decide la importancia.

La lección del heap

El heap nos enseña que el orden no siempre significa tener todo perfectamente acomodado.

A veces, el problema no exige saber dónde está cada elemento en un orden total. A veces solo necesitamos saber cuál debe salir primero.

El array nos enseñó el poder del índice. La lista enlazada nos enseñó el valor del enlace. La pila nos enseñó el valor del retorno. La cola nos enseñó el valor del turno. La tabla hash nos enseñó el poder de la clave. El árbol binario de búsqueda nos enseñó el valor de comparar. El heap nos enseña el valor de priorizar.

En software, como en la vida, no todo se atiende por orden de llegada. Algunas cosas tienen mayor urgencia, mayor peso o mayor importancia.

El heap nos recuerda que una buena estructura no siempre ordena todo; a veces basta con mantener visible lo que debe atenderse primero.

Próxima entrega

En el próximo artículo de esta saga estudiaremos el graph, o grafo. Allí veremos una de las estructuras más poderosas para representar conexiones, rutas, redes sociales, dependencias y caminos.

Pasaremos de priorizar elementos a descubrir relaciones.