heap_example.C File Reference

Priority Queues: Binary Heap vs Fibonacci Heap. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <chrono>
#include <random>
#include <tpl_dynBinHeap.H>
#include <tpl_fibonacci_heap.H>
#include <tclap/CmdLine.h>

Include dependency graph for heap_example.C:

Go to the source code of this file.

Classes
struct	Task
	Task with priority for job scheduling. More...

Functions
ostream &	operator<< (ostream &os, const Task &t)
void	demo_binary_heap ()
	Demonstrate basic binary heap operations.
void	demo_fibonacci_heap ()
	Demonstrate Fibonacci heap operations.
void	demo_event_simulation ()
	Practical example: Event-driven simulation.
void	demo_performance_comparison (int n)
	Performance comparison between heap types.
void	demo_max_heap ()
	Demonstrate max-heap usage.
int	main (int argc, char *argv[])

Detailed Description

Priority Queues: Binary Heap vs Fibonacci Heap.

This example compares two fundamental heap implementations for priority queues, demonstrating when to use each and their performance characteristics. Priority queues are essential for many algorithms, and choosing the right implementation can significantly impact performance.

What is a Priority Queue?

A priority queue is a data structure that supports:

• insert(x): Add element with priority
• extract_min(): Remove and return element with highest priority
• decrease_key(x, k): Lower priority of element x to k
• find_min(): View highest priority element without removal

Elements are ordered by priority (typically: lower value = higher priority).

Two Heap Implementations Compared

Binary Heap

A complete binary tree stored in an array satisfying the heap property (parent ≤ children for min-heap).

Characteristics:

• Simple: Easy to understand and implement
• Cache-friendly: Array-based, good memory locality
• Predictable: O(log n) worst-case for all operations
• Space efficient: No pointer overhead

Operations:

• insert: O(log n) - bubble up
• extract_min: O(log n) - bubble down
• decrease_key: O(log n) - bubble up
• find_min: O(1) - root element

Fibonacci Heap

A more sophisticated heap structure using a collection of trees with lazy consolidation, achieving better amortized complexity.

Characteristics:

• Complex: More sophisticated implementation
• Amortized performance: Better average-case complexity
• Lazy consolidation: Defers work until necessary
• Theoretical optimal: Best known complexity for some operations

Operations:

• insert: O(1) amortized - just add to root list
• extract_min: O(log n) amortized - consolidate trees
• decrease_key: O(1) amortized - cut and promote
• find_min: O(1) - pointer to minimum
• merge: O(1) - concatenate root lists

Complexity Comparison

Operation	Binary Heap	Fibonacci Heap	Winner
insert	O(log n)	O(1) amortized	Fibonacci
find-min	O(1)	O(1)	Tie
extract-min	O(log n)	O(log n) amortized	Tie
decrease-key	O(log n)	O(1) amortized	Fibonacci
merge	O(n)	O(1)	Fibonacci

Note: Amortized complexity means average over many operations. Individual operations may be slower, but overall performance is better.

When to Use Which?

Use Binary Heap When:

✅ General-purpose priority queue

• Most common use case
• Simple implementation preferred
• Predictable performance needed

✅ Heap sort

• In-place sorting algorithm
• O(n log n) time, O(1) extra space

✅ Decrease-key is rare

• Most operations are insert/extract
• Few or no decrease-key operations

✅ Memory matters

• Array-based, no pointer overhead
• Better cache performance

Use Fibonacci Heap When:

✅ Many decrease-key operations

• Algorithms like Dijkstra's (many decrease-key calls)
• Prim's MST algorithm
• When decrease-key dominates runtime

✅ Theoretical optimality needed

• Academic/research applications
• When best complexity matters

✅ Merge operations needed

• Frequently merging heaps
• O(1) merge is critical

Real-World Performance

Despite better theoretical complexity, Fibonacci heaps often have:

• Higher constant factors: More complex operations
• Worse cache performance: Pointer-based structure
• More memory overhead: Multiple pointers per node

Result: Binary heaps are often faster in practice for typical workloads!

Rule of thumb: Use binary heap unless you have a specific need for Fibonacci heap's advantages (many decrease-key operations).

Applications

Binary Heap Applications

• Task scheduling: Operating system schedulers
• Event simulation: Discrete event simulation
• Graph algorithms: A* search, some shortest path variants
• Heap sort: Efficient in-place sorting

Fibonacci Heap Applications

• Dijkstra's algorithm: Many decrease-key operations
• Prim's MST: Minimum spanning tree with decrease-key
• Network flow: Some flow algorithms benefit
• Theoretical algorithms: When optimal complexity matters

Example: Dijkstra's Algorithm

Dijkstra's algorithm for shortest paths:

• Operations: Many decrease-key calls (update distances)
• Binary heap: O(E log V) total
• Fibonacci heap: O(E + V log V) total (better!)

For dense graphs (E ≈ V²), Fibonacci heap provides significant speedup.

Usage

# Run all demos (default if no flags are given)
./heap_example
 
# Explicitly run all demos
./heap_example --all
 
# Run specific demos
./heap_example --basic
./heap_example --fibonacci
./heap_example --simulation
./heap_example --performance
./heap_example --max
 
# Show help
./heap_example --help
 
# Performance comparison size
./heap_example --performance --count 50000

See also

tpl_binHeap.H Binary heap implementation

tpl_dynBinHeap.H Dynamic binary heap

tpl_fibonacci_heap.H Fibonacci heap implementation

writeHeap.C Heap visualization

Author

Leandro Rabindranath León

Definition in file heap_example.C.

Function Documentation

demo_binary_heap()

void demo_binary_heap

(

)

Demonstrate basic binary heap operations.

Definition at line 241 of file heap_example.C.

References Aleph::DynList< T >::get(), Aleph::DynBinHeap< T, Compare >::get(), Aleph::DynList< T >::insert(), Aleph::DynBinHeap< T, Compare >::insert(), Aleph::HTList::is_empty(), Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::GenBinHeap< NodeType, Key, Compare >::size(), and Aleph::DynBinHeap< T, Compare >::top().

Referenced by main().

demo_event_simulation()

void demo_event_simulation

(

)

Practical example: Event-driven simulation.

Definition at line 370 of file heap_example.C.

References Aleph::DynList< T >::get(), Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), and operator<().

Referenced by main().

demo_fibonacci_heap()

void demo_fibonacci_heap

(

)

Demonstrate Fibonacci heap operations.

Definition at line 296 of file heap_example.C.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::HTList::size().

Referenced by main().

demo_max_heap()

void demo_max_heap

(

)

Demonstrate max-heap usage.

Definition at line 516 of file heap_example.C.

References Aleph::DynList< T >::get(), Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::DynList< T >::top().

Referenced by main().

demo_performance_comparison()

void demo_performance_comparison

(

int

n

)

Performance comparison between heap types.

Definition at line 412 of file heap_example.C.

References Aleph::Fibonacci_Heap< T, Compare >::decrease_key(), Aleph::Fibonacci_Heap< T, Compare >::extract_min(), Aleph::DynBinHeap< T, Compare >::get(), Aleph::DynBinHeap< T, Compare >::insert(), Aleph::Fibonacci_Heap< T, Compare >::insert(), Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty(), Aleph::Fibonacci_Heap< T, Compare >::is_empty(), and Aleph::maps().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 558 of file heap_example.C.

References demo_binary_heap(), demo_event_simulation(), demo_fibonacci_heap(), demo_max_heap(), demo_performance_comparison(), and Aleph::maps().

operator<<()

ostream & operator<<	(	ostream &	os,
		const Task &	t
	)

Definition at line 233 of file heap_example.C.

References Task::duration_ms, Aleph::maps(), Task::name, and Task::priority.