Priority Queue Comparison: Binary Heap vs. Fibonacci Heap

Overview

This project compares the performance of two different priority queue implementations:

• Binary Heap

• Fibonacci Heap

The goal is to evaluate their performance across different operations and analyze their theoretical vs. experimental behavior.

---

Research Paper Available

A detailed research paper is included in this repository, discussing the design, analysis, and benchmarking of both heap implementations. Download (PDF)

---

Features:

Binary and Fibonacci Heap Implementation

• Insert (insert) Insert a new element into the heap

• Extract-Min (extract) Extract the root element of the heap

• Decrease-key (decrease_key) Decrease the key of a given element

• Merge (merge) Merge another heap for the same type

• Display (display) Return a string representation of the heap

---

Benchmarks:

All benchmarks below were run on descending-ordered input to simulate worst-case scenarios. Each data point is averaged over multiple trials and input sizes.

• Insert (benchmark_insert)
  Measures total time to insert n descending elements into an empty heap.

• Extract-Min (benchmark_extract)
  Inserts n elements, then extracts the minimum until the heap is empty. Reflects consolidation cost in Fibonacci Heaps.

• Merge (benchmark_merge)
  Merges two pre-filled heaps of equal size. Evaluated for both Binary and Fibonacci Heaps.

• Decrease-Key (benchmark_[heap]_decrease_key_timed_isolated)
  Measures the average time for a single decrease-key operation on a freshly constructed heap.
  For Fibonacci Heaps, this captures cascading cuts.

• Memory Usage (benchmark_memory_usage)
  Peak memory usage measured using tracemalloc during heap construction.

---

Swap/Cut Cost Benchmarks

These benchmarks isolate the structural cost (not runtime) of a single decrease-key call.

• Fibonacci Heap Cuts (benchmark_fibonacci_decrease_key_cuts_isolated)
  Tracks how many cuts (i.e., child removals) happen during a decrease-key.

• Binary Heap Swaps (benchmark_binary_decrease_key_swaps_isolated)
  Tracks how many swaps are needed to bubble up a worst-case node.

These tests help demonstrate the hidden structural cost behind decrease_key, which runtime benchmarks might not capture alone.

---

Realistic Benchmark: Dijkstra's Algorithm

We ran a version of Dijkstra’s Algorithm with lazy deletion and periodic heap merges:

• Benchmarks tested across graphs of varying size and density
• Compares total runtime and peak memory usage
• Uses both Binary and Fibonacci Heaps as the underlying priority queue

This shows how each heap performs in real-world graph applications, especially when merge frequency is high.

---

Dependencies:

Standard Library

• abc – Provides ABC (Abstract Base Classes)
• gc – Garbage collection interface
• os – Interact with the operating system
• sys – System-specific parameters and functions
• time – Time-related functions for performance benchmarking
• random – Random number generation
• tracemalloc – Memory profiling and tracking
• typing – Provides type hints (List, Optional, Generic, TypeVar)

External Libaries

• matplotlib Data visualization (for plotting graphs)
• seaborn Statistical data visualization (enhanced graph aesthetics).
• pandas Data analysis and manipulation.
• tkinters GUI framework (used for creating the benchmark viewer).

Installing External Libaries

Run the following command to install are the required external libaries:

pip install -r requirements.txt

---

Contributions

• Miller Fourie: Core heap implementations, benchmarking code, Dijkstra's algorithm, runtime measurement, data analysis.
• Owen Zgurski: Analyzed and validated merge benchmarks.
• kobs3720: Evaluated decrease-key performance and structural impact.