This project provides comprehensive implementations of advanced heap data structures, demonstrating their unique properties, operations, and performance characteristics. Each implementation is designed for academic study and includes detailed documentation, complexity analysis, and practical examples.
- Collection of binomial trees satisfying min-heap property
- Efficient union operation in O(log n) time
- Supports insert, find-min, delete-min, and merge operations
- Key Feature: Optimal for frequent merge operations
- Lazy approach with amortized constant time for insert and decrease-key
- Exceptional performance for graph algorithms (Dijkstra's, Prim's)
- Amortized O(1) for insert, find-min, merge, and decrease-key
- Amortized O(log n) for delete-min
- Key Feature: Best amortized complexity for priority queue operations
- Complete binary tree with alternating min/max levels
- Double-ended priority queue functionality
- O(1) access to both minimum and maximum elements
- O(log n) insertion and deletion
- Key Feature: Efficient access to both extremes
- Simple multiway tree structure
- Excellent practical performance despite theoretical bounds
- Easy to implement compared to Fibonacci heaps
- Good for priority queues with frequent key updates
- Key Feature: Simplicity with good practical performance
- Binary tree with "leftist property" for efficient merging
- Null path length (npl) maintained for balance
- O(log n) merge operation
- Key Feature: Optimized specifically for heap merging
- Self-adjusting variant of leftist heap
- No explicit balance information needed
- Amortized O(log n) for all operations
- Simpler implementation than leftist heap
- Key Feature: Self-balancing with minimal overhead
advanced_heap_operations/
├── README.md # This file
├── requirements.txt # Python dependencies
├── heaps/
│ ├── __init__.py
│ ├── binomial_heap.py # Binomial heap implementation
│ ├── fibonacci_heap.py # Fibonacci heap implementation
│ ├── min_max_heap.py # Min-Max heap implementation
│ ├── pairing_heap.py # Pairing heap implementation
│ ├── leftist_heap.py # Leftist heap implementation
│ └── skew_heap.py # Skew heap implementation
├── tests/
│ ├── __init__.py
│ └── test_fibonacci_heap.py # Example test file
├── examples/
│ ├── basic_operations.py # Basic usage examples
│ ├── graph_algorithms.py # Dijkstra's and Prim's with heaps
│ └── performance_comparison.py # Benchmark different heaps
├── visualization/
│ ├── heap_visualizer.py # Visualize heap structures
│ └── performance_plots.py # Generate performance graphs
└── docs/
├── 01_problem_definition.md # Problem definition
├── 02_algorithm_design.md # Algorithm design
├── 03_complexity_analysis.md # Detailed complexity analysis
├── 04_test_outputs.md # Test outputs and results
└── ACADEMIC_REPORT.md # Complete academic report
| Operation | Binomial | Fibonacci | Min-Max | Pairing | Leftist | Skew |
|---|---|---|---|---|---|---|
| Insert | O(log n) | O(1)* | O(log n) | O(1)* | O(log n) | O(log n)* |
| Find-Min | O(log n) | O(1) | O(1) | O(1) | O(1) | O(1) |
| Delete-Min | O(log n) | O(log n)* | O(log n) | O(log n)* | O(log n) | O(log n)* |
| Decrease-Key | O(log n) | O(1)* | O(log n) | O(log n)* | O(log n) | O(log n)* |
| Merge | O(log n) | O(1)* | O(n) | O(1)* | O(log n) | O(log n)* |
*Amortized time complexity
Use the automated setup script:
cd ads/advanced_heap_operations
./setup.shThis script will:
- Create a virtual environment
- Install all dependencies
- Verify the installation
# Navigate to the project directory
cd ads/advanced_heap_operations
# Create a virtual environment
python3 -m venv venv
# Activate the virtual environment
source venv/bin/activate # On macOS/Linux
# OR
venv\Scripts\activate # On Windows
# Install dependencies
pip install -r requirements.txt# Install with user flag
pip3 install --user -r requirements.txt
# OR use break-system-packages (not recommended)
pip3 install --break-system-packages -r requirements.txt# Install pipx if not already installed
brew install pipx
# Install packages
pipx install matplotlib numpyNote: On macOS with Homebrew-managed Python, using a virtual environment is strongly recommended to avoid conflicts with system packages.
Launch the interactive web interface to run examples and code through your browser:
cd ads/advanced_heap_operations
./start_web_interface.shThen open your browser to: http://localhost:5001
Note: macOS AirPlay Receiver occupies port 5000 by default. The server auto-detects and uses the next available port (5001). The exact URL is printed in the terminal on startup.
Features (7 tabs):
- ⚙️ Basic Operations — run insert, find-min, delete-min, merge demos for all 6 heaps
- 🗺️ Graph Algorithms — Dijkstra's shortest path and Prim's MST
- 📈 Performance Comparison — benchmark all 6 heaps with embedded charts (5 charts auto-refresh after each run)
- 🎮 Heap Playground — select any heap type and interactively run Insert, Find Min, Delete Min, Find Max (Min-Max only), Reset
- 💻 Interactive Code — Python console with all 6 heap classes pre-imported
- 📊 Heap Information — time complexity tables and use-case recommendations
- 🧪 Run Tests — 18-test Fibonacci Heap suite with colour-coded results
See web_interface/README.md for more details.
# Navigate to the project directory
cd ads/advanced_heap_operations
# Run basic operations examples
python examples/basic_operations.py
# Run graph algorithms examples
python examples/graph_algorithms.py
# Run performance comparison
python examples/performance_comparison.pyfrom heaps.fibonacci_heap import FibonacciHeap
from heaps.min_max_heap import MinMaxHeap
# Fibonacci Heap Example
fib_heap = FibonacciHeap()
fib_heap.insert(10)
fib_heap.insert(5)
fib_heap.insert(20)
print(f"Minimum: {fib_heap.find_min()}") # Output: 5
fib_heap.delete_min()
# Min-Max Heap Example
mm_heap = MinMaxHeap()
mm_heap.insert(10)
mm_heap.insert(5)
mm_heap.insert(20)
print(f"Minimum: {mm_heap.find_min()}") # Output: 5
print(f"Maximum: {mm_heap.find_max()}") # Output: 20# Run all tests with unittest
python -m unittest discover tests/
# Run specific heap tests
python -m unittest tests.test_fibonacci_heap -v
# Or run the test file directly
python tests/test_fibonacci_heap.py
# If you have pytest installed (optional)
python -m pytest tests/ -v
python -m pytest tests/test_fibonacci_heap.py -vSee examples/basic_operations.py for comprehensive examples of all heap operations.
python examples/basic_operations.pySee examples/graph_algorithms.py for Dijkstra's and Prim's algorithm implementations.
python examples/graph_algorithms.pySee examples/performance_comparison.py for benchmarking different heap implementations.
python examples/performance_comparison.pyGenerate performance plots:
from visualization.performance_plots import plot_comparison
# Your performance data
results = {
'Fibonacci Heap': {'insert': [0.001, 0.002], 'delete_min': [0.003, 0.004]},
'Binomial Heap': {'insert': [0.002, 0.003], 'delete_min': [0.004, 0.005]}
}
plot_comparison(results, save_path='comparison.png')- Binomial Heap: When you need frequent merge operations with good worst-case guarantees
- Fibonacci Heap: For graph algorithms (Dijkstra's, Prim's) where decrease-key is frequent
- Min-Max Heap: When you need efficient access to both minimum and maximum elements
- Pairing Heap: When you want simplicity with good practical performance
- Leftist Heap: When merging is the primary operation and you want predictable performance
- Skew Heap: When you want a simple self-adjusting heap with good amortized performance
- A binomial tree Bₖ has 2^k nodes
- Root has degree k with children B₀, B₁, ..., Bₖ₋₁
- Height is k
- Delays consolidation until delete-min
- Maintains a collection of heap-ordered trees
- Uses cascading cuts for decrease-key
- Even levels (0, 2, 4, ...) are min levels
- Odd levels (1, 3, 5, ...) are max levels
- Root is always the minimum element
- For every node, npl(left child) ≥ npl(right child)
- Ensures the right path is always short
- Enables efficient merging
Typical performance on modern hardware (operations per second):
| Heap Type | Insert (1M ops) | Delete-Min (1M ops) | Merge (10K ops) |
|---|---|---|---|
| Binomial | ~500K/sec | ~400K/sec | ~50K/sec |
| Fibonacci | ~2M/sec | ~300K/sec | ~1M/sec |
| Min-Max | ~800K/sec | ~600K/sec | ~10K/sec |
| Pairing | ~1.5M/sec | ~500K/sec | ~800K/sec |
| Leftist | ~600K/sec | ~400K/sec | ~100K/sec |
| Skew | ~700K/sec | ~450K/sec | ~120K/sec |
Note: Actual performance varies based on data patterns and hardware
- Binomial Heaps: Vuillemin, J. (1978). "A data structure for manipulating priority queues"
- Fibonacci Heaps: Fredman, M. L., & Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms"
- Min-Max Heaps: Atkinson, M. D., et al. (1986). "Min-max heaps and generalized priority queues"
- Pairing Heaps: Fredman, M. L., et al. (1986). "The pairing heap: A new form of self-adjusting heap"
- Leftist Heaps: Crane, C. A. (1972). "Linear lists and priority queues as balanced binary trees"
- Skew Heaps: Sleator, D. D., & Tarjan, R. E. (1986). "Self-adjusting heaps"
This is an academic project. Contributions for educational improvements are welcome:
- Enhanced documentation
- Additional test cases
- Performance optimizations
- Visualization improvements
MIT License - Free for academic and educational use
Created as part of Advanced Data Structures coursework
- Course materials from MIT OCW, Stanford, and CMU
- Classic papers on heap data structures
- Open-source implementations for reference