How to Implement Fibonacci Heap in Python

Submitted by razormist on Friday, March 6, 2026 - 22:41.

In this tutorial, we will learn how to program “How to Implement a Fibonacci Heap in Python.” The main objective is to implement a Fibonacci heap data structure. This tutorial will guide you step by step through the process of implementing a Fibonacci heap. By the end of this tutorial, you will have a solid understanding of how Fibonacci heaps work in Python, helping you strengthen your problem-solving abilities and improve your overall coding skills in data structure implementation.

This topic is straightforward and easy to understand. By simply following the instructions provided, you will be able to complete it with ease. The program will guide you step by step through the process of implementing a Fibonacci heap. So, let’s dive into the coding process and start implementing the solution to gain a deeper understanding of data structures in Python.

Getting Started:

First you will have to download & install the Python IDLE's, here's the link for the Integrated Development And Learning Environment for Python https://www.python.org/downloads/.

Creating Main Function

This is the main function of the application. The following code will display a simple GUI in terminal console that will display program. To do this, simply copy and paste these blocks of code into the IDLE text editor.

import math
 
class FibonacciTree:
    def __init__(self, key):
        self.key = key
        self.children = []
        self.order = 0
 
    def add_at_end(self, t):
        self.children.append(t)
        self.order = self.order + 1
 
 
class FibonacciHeap:
    def __init__(self):
        self.trees = []
        self.least = None
        self.count = 0
 
    def insert(self, key):
        new_tree = FibonacciTree(key)
        self.trees.append(new_tree)
 
        if self.least is None or key < self.least.key:
            self.least = new_tree
 
        self.count += 1
 
    def get_min(self):
        if self.least is None:
            return None
        return self.least.key
 
    def extract_min(self):
        smallest = self.least
 
        if smallest is not None:
            for child in smallest.children:
                self.trees.append(child)
 
            self.trees.remove(smallest)
 
            if self.trees == []:
                self.least = None
            else:
                self.least = self.trees[0]
                self.consolidate()
 
            self.count -= 1
            return smallest.key
 
    def consolidate(self):
        aux = (floor_log2(self.count) + 1) * [None]
 
        while self.trees != []:
            x = self.trees[0]
            order = x.order
            self.trees.remove(x)
 
            while aux[order] is not None:
                y = aux[order]
 
                if x.key > y.key:
                    x, y = y, x
 
                x.add_at_end(y)
                aux[order] = None
                order += 1
 
            aux[order] = x
 
        self.least = None
 
        for k in aux:
            if k is not None:
                self.trees.append(k)
 
                if self.least is None or k.key < self.least.key:
                    self.least = k
 
 
def floor_log2(x):
    return math.frexp(x)[1] - 1
 
 
# Main Program
while True:
 
    print("\n================= Implement Fibonacci Heap =================\n")
 
    fheap = FibonacciHeap()
 
    print("Menu")
    print("insert <data>")
    print("min get")
    print("min extract")
    print("quit")
 
    while True:
        do = input("\nWhat would you like to do? ").split()
 
        if len(do) == 0:
            continue
 
        operation = do[0].lower()
 
        if operation == "insert":
            data = int(do[1])
            fheap.insert(data)
            print("Inserted:", data)
 
        elif operation == "min":
            suboperation = do[1].lower()
 
            if suboperation == "get":
                print("Minimum value:", fheap.get_min())
 
            elif suboperation == "extract":
                print("Minimum value removed:", fheap.extract_min())
 
        elif operation == "quit":
            break
 
        else:
            print("Invalid command.")
 
    # Try Again Option
    opt = input("\nDo you want to try again? (yes/no): ").strip().lower()
 
    if opt == "no":
        print("Exiting program...")
        break
    elif opt != "yes":
        print("Invalid choice. Exiting program...")
        break

This program demonstrates the implementation of a Fibonacci Heap, an advanced data structure used for efficiently managing priority queues. It defines two main classes: `FibonacciTree`, which represents individual nodes that store a key, children, and order, and `FibonacciHeap`, which manages a collection of these trees. The heap supports core operations such as inserting elements, retrieving the minimum value, and extracting the minimum element. When the minimum element is removed, the program reorganizes the remaining trees through a consolidation process that merges trees of the same order to maintain the heap structure. The program also includes a menu-driven interface that allows users to interactively insert values, view the minimum element, or extract the smallest value from the heap. Additionally, it provides an option to restart or exit the program, making it a practical example for understanding how Fibonacci Heaps manage data efficiently while demonstrating fundamental concepts of advanced heap structures in Python.

Output:

There you have it we successfully created How to Implement Fibonacci Heap in Python. I hope that this simple tutorial help you to what you are looking for. For more updates and tutorials just kindly visit this site. Enjoy Coding!

More Tutorials for Python Language

Python Tutorials