Skip to content

Latest commit

 

History

History
35 lines (25 loc) · 1.34 KB

README.md

File metadata and controls

35 lines (25 loc) · 1.34 KB

Fibonacci Heap Demo

This project is to construct a basic Fibonacci Heap using simple classes made from scratch.

This software is licensed under GPL3.0-only. Licensing information can be found in COPYING file. All sources for this project can be obtained here

Any modifications to this project, for any reason, must be licensed under the GPL 3.0 license only.

Copyright (C) 2023 James Green.

Overview

A Fibonacci heap is a heap-like datastructure (typically used for priority queses) that has the advantages of performing most basic operations in constant time. These operations include

  • Insert
  • Decrease Key
  • Remove

Other operations of a logarithmic time compelxity. These operations include:

  • ExtractMin

The benefits of this data structure really only become apparent with large data sets.

Classes in this project

There are several data structures needed to make up a fibonacci heap.

  • Double Linked List
  • Binary Tree/Priority Queue

For the purposes of this project's documentation, the linked list will be referred to as "The Master Array" and the elements of that list will be referred to as "sub-trees".

Project Scope

This project is meant to provide a simple demonstration of the Fibonacci heap. As such, it will work only with integers. This will be a console only application.