nkokor / fibonacci_heap

Python implementation of Fibonacci Heap

fibonacci_heap

This repository contains my implementation of Fibonacci Heap data structure in Python, done as part of the Advanced Algorithms and Data Structures course at the Faculty of Electrical Engineering in Sarajevo. The implementation was modeled after the pseudocode found in the book "Introduction to Algorithms ".

Fibonacci Heap

A Fibonacci Heap is a versatile data structure that provides efficient implementations of various priority queue operations such as insert, extract minimum, decrease key, and union. It is particularly useful in algorithms like Dijkstra's shortest path and Prim's minimum spanning tree.

📁 Project structure

The project is organized with the following directory structure:

Fibonacci_heap/
│
├── main.py
├── tests/
│   └── test.py
│
└── classes/
    ├── FibNode.py
    └── FibHeap.py

• main.py - main entry point, contains a simple example of a Fibonacci Heap.

• tests/ - holds unit tests for the project

  • test.py - contains 12 unit tests testing different scenarios

• classes/ - contains the main classes required for implementation

  • FibNode.py - definition of the node structure used in the Fibonacci Heap
  • FibHeap.py - implementation of the Fibonacci Heap data structure

🔎 Implementation details

The Fibonacci Heap itself is represented by FibHeap class with following attributes:

• root_list - a pointer to one of the nodes in a doubly linked list of root nodes
• min - a pointer to the node with minimum key value
• n - number of nodes in the heap

Singular nodes are instances of class FibNode, representing a node of a Fibonacci Heap using the following attributes:

• key - key value of node
• parent - parent of node
• child - pointer to one of the nodes in a doubly linked list of child nodes
• left - left sibling of node
• right - right sibling of node
• degree - degree of node (number of node's children)
• marked - mark of node (True or False)
• id - unique id of node

Main Methods

• fib_heap_insert(key) - inserts new node with given key into heap
• fib_extract_min() - removes and returns node with minimum key
• fib_heap_decrease_key(key, new_key) - decreases key value of node with given key to new key value
• fib_heap_delete(key) - removes node with given key from heap
• fib_heap_union(h1, h2) - performs concatenation of two given heaps into a new heap