Soft Heap -- Visualizador Interactivo Moderno

Implementación del Binary Soft Heap (Kaplan-Zwick-Tarjan) aplicado al algoritmo de Prim para árboles de expansión mínima,
con una interfaz web moderna en Vue 3 y un benchmark nativo comparativo.

---

Tabla de Contenidos

1. Que es este proyecto?
2. Inicio rapido (sin compilar nada)
3. Estructura del proyecto
4. Que es un Soft Heap?
5. Codigo del Soft Heap explicado
6. Operaciones del Soft Heap
7. Ejemplo paso a paso
8. Conexion con el MST de Prim
9. Comparacion de algoritmos
10. El visualizador
11. Compilacion nativa (benchmark)
12. Dataset
13. Problemas frecuentes
14. Referencias

---

1. Que es este proyecto?

Este proyecto implementa la estructura de datos Binary Soft Heap del paper de Kaplan, Zwick y Tarjan (2013) y la usa para ejecutar el algoritmo de Prim (arbol de expansion minima).

El Soft Heap es una cola de prioridad aproximada: deliberadamente "corrompe" algunas claves para lograr inserciones en O(1) amortizado, a cambio de que algunas extracciones devuelvan items cuyas claves fueron artificialmente aumentadas.

El proyecto tiene dos partes:

Componente	Descripcion
Visualizador Web	Aplicacion interactiva en el navegador donde se puede ver paso a paso como Prim encuentra el MST mientras el Soft Heap se reestructura internamente. Compilado a WebAssembly con Emscripten.
Benchmark Nativo	Ejecutable C++ que mide el rendimiento de Prim usando 3 colas de prioridad distintas: Soft Heap, Binary Heap y Fibonacci Heap.

---

2. Inicio rápido (Desarrollo Frontend)

Para ejecutar el visualizador moderno:

# 1. Navega a la carpeta web
cd web

# 2. Instala dependencias
npm install

# 3. Inicia el servidor de desarrollo
npm run dev

Abre el navegador en la URL indicada por Vite (normalmente http://localhost:5173).

---

3. Estructura del proyecto

soft-heap/
|
|-- src/                          # Código fuente C++ (Algoritmo Puro)
|   |-- soft_heap.h               # IMPLEMENTACIÓN SIMPLIFICADA (Estilo Libro)
|   |-- graph.h                   # Estructura del grafo y parser KONECT
|   |-- prim_soft_heap.cpp        # Algoritmo de Prim nativo
|   |-- fibonacci_heap.h          # Fibonacci Heap para benchmark
|   |-- prim_binary_heap.h        # Prim con Binary Heap
|   |-- prim_fibonacci.h          # Prim con Fibonacci Heap
|   |-- benchmark.cpp             # Suite de pruebas de rendimiento
|   +-- ejemplos_paper.cpp        # Casos de prueba del paper original
|
|-- web/                          # Visualizador Web (Vue 3 + Vite)
|   |-- src/
|   |   |-- scripts/
|   |   |   |-- softheap.js       # Lógica pura del Soft Heap en JS
|   |   |   |-- AnimatedSoftHeap.js # Lógica de animación interconectada
|   |   |   +-- CytoscapeFacade.js # Abstracción de visualización con Cytoscape
|   |   +-- views/
|   |       +-- SoftHeapView.vue  # Interfaz principal de la aplicación
|
|-- CMakeLists.txt                # Sistema de compilación nativo
+-- README.md                     # Este archivo

---

4. ¿Qué es un Soft Heap?

Un Soft Heap es una cola de prioridad (como un min-heap) pero con una diferencia fundamental: se le permite aumentar las claves de algunos elementos. A cambio de esta relajación, las inserciones son más rápidas.

Operación	Binary Heap	Fibonacci Heap	Soft Heap
insert	O(log n)	O(1) amortizado	O(1) amortizado
find-min	O(1)	O(1)	O(1)
extract-min	O(log n)	O(log n) amortizado	O(log(1/$\epsilon$)) amortizado
decrease-key	O(log n)	O(1) amortizado	No soportado

El parámetro epsilon

El Soft Heap recibe un parámetro epsilon ($0 < \epsilon < 1$) que controla cuánta corrupción se permite:

• epsilon pequeño (ej. 0.01): muy pocas claves corrompidas, casi exacto, pero más lento.
• epsilon grande (ej. 0.9): muchas corrupciones, más rápido, pero las claves reportadas pueden estar infladas.

La garantía formal es: como máximo $\epsilon \cdot n$ items tendrán claves corrompidas en cualquier momento ($n$ = total de inserciones).

El umbral interno se calcula como:

T = ceil( log2(3 / epsilon) )

Para epsilon = 0.5, T = 3. Nodos con rango par mayor que T sufrirán double-fill, que es el mecanismo matemático que permite agrupar varios items en un solo nodo, causando la corrupción de forma controlada.

---

5. Implementación Simplificada

A diferencia de la propuesta original de Chazelle basada en colas binomiales, esta implementación se rige por el paper "Soft Heaps Simplified" (Kaplan, Tarjan, Zwick, 2013) que utiliza una estructura de árboles binarios.

El uso de árboles binarios reduce drásticamente la complejidad estructural, facilitando su comprensión académica y práctica sin sacrificar las garantías de rendimiento de sus operaciones asintóticas (inserciones en tiempo O(1) amortizado). En lugar de lidiar con un bosque binomial entrelazado, el algoritmo opera sobre un bosque de árboles binarios estándar donde la "corrupción" y superposición de datos es controlada estrictamente en subárboles asimétricos durante extracciones, haciéndolo altamente eficiente, predecible y analizable.

---

6. Conexión con el MST de Prim

En prim_soft_heap.cpp, el Soft Heap reemplaza a la cola de prioridad tradicional. Prim es robusto a la corrupción del Soft Heap porque simplemente descarta ítems que apuntan a vértices ya incluidos en el MST:

SoftHeap H(epsilon);
in_mst[0] = true;

for (const Edge& e : g.neighbors(0))
    H.insert(e.weight, e.to);

while (!H.is_empty() && aristas < V - 1) {
    Item* item = H.extractMin();
    int v = item->node;
    if (in_mst[v]) continue; // Filtrado de corrupción
    in_mst[v] = true;
    // ...
}

---

7. Interfaz del Visualizador

La interfaz web ha sido rediseñada para ofrecer una experiencia académica premium:

• Layout de dos columnas: Grafo interactivo a la izquierda (Cytoscape.js) y Sidebar de información a la derecha (Vue 3).
• Barra de Herramientas: Control de reproducción (Play, Pause, Step, Speed) e input dinámico de Epsilon.
• Panel de Pseudocódigo: Referencia constante al algoritmo mientras se ejecuta.
• Historial en Vivo: Registro de cada operación (insert, extract-min) para trazabilidad total.

---

8. Compilación Nativa (Benchmark)

Requisitos

• Compilador C++17 (GCC, Clang o MSVC)
• CMake >= 3.20

Compilar y Ejecutar

# Desde la raíz del proyecto
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build

# Ejecutar ejemplos del paper
./build/ejemplos

# Ejecutar el benchmark comparativo
./build/benchmark

---

9. Créditos e Inspiración

La visualización y gran parte de la lógica de animación están inspiradas en el trabajo de:

Shane McCann
Soft Heap Visualizer (2023)
GitHub Repository
Live Demo

Agradecimientos especiales por su elegante enfoque en la animación de estructuras de datos complejas.

---

10. Referencias

• Haim Kaplan, Robert E. Tarjan, and Uri Zwick. 2013. Soft Heaps Simplified. SIAM Journal on Computing 42, 4 (January 2013), 1660–1673. https://doi.org/10.1137/120880185
• Chazelle, B. (2000). The Soft Heap: An Approximate Priority Queue with Optimal Error Rate. JACM.
• Shane McCann (2023). Soft Heap Visualizer. github.com/mccannsa/soft-heap-visualizer.

---

_{Proyecto para EDA -- Estructura de Datos y Algoritmos}