Add Fibonacci Heap

[czgdp1807]

Description of the problem

Example of the problem

References/Other comments

Can be done only after #36 https://en.wikipedia.org/wiki/Fibonacci_heap

[Saptashrungi]

Hey, I am interested in working on this issue. I will propose the design for the same soon.

[czgdp1807]

Let me know if you need any help.

[iamrajiv]

@czgdp1807 I would like to work on this. Is it available?

[czgdp1807]

@iamrajiv Yes, sure. Please come up with a design for the Fibonacci Heap. You can refer and take inspiration from https://github.com/codezonediitj/pydatastructs/issues/36#issuecomment-567534858

[nehasangeetajha]

is this one available? @czgdp1807 I would like to work on this

[czgdp1807]

@nehasangeetajha Since no one has proposed an API design for fibonacci heap, you can come up with your own and start working on this issue. You may refer to the design of Binomial heap here.

[nehasangeetajha]

I have come up with the following API design. Please have a look.

We will have a class Fibonacci heap with the following members:

Fibonacci Heap Node node will represent the nodes in the fibonacci heap. They will have following data members:

1. key: key of the current node
2. value: the value of the current node
3. parent: reference to the parent of the current node
4. degree: Degree of the current node (to how many nodes is it connected)
5. mark: If is it marked or not ( bool type)

• Variables : min_node , total_nodes

The class will have following methods:

• iterate : A function to iterate over the heap (or DLL here)

• find_min : A function to find minimum for the current node

• extract_min: A function to remove (or extract) minimum node from the heap

• insert: A function to insert new node at its correct position

• decrease_key: Modify key of the current node

• cut : If a child node becomes smaller than its parent node we cut this child node off and bring it up to the root list

• heap-link:actual linking of one node to another

• merge_with_root_list

• merge_with_child_list

• remove_from_root_list

• remove_from_child_list

It is just a rough approach. Please suggest improvements if any. Thank you

[czgdp1807]

• cut : If a child node becomes smaller than its parent node we cut this child node off and bring it up to the root list
• heap-link:actual linking of one node to another
• merge_with_root_list
• merge_with_child_list
• remove_from_root_list
• remove_from_child_list

IMO, the above methods need not to be "public" i.e., we can start their name with a _. Rest looks good.

[nehasangeetajha]

Ok @czgdp1807 I will start implementing it then, making these private

[HarsheetKakar]

@nehasangeetajha are you working on it?

[nehasangeetajha]

Yes, I am working Will come up with PR soon

[kichloo]

@czgdp1807 Can I work on this issue?

[czgdp1807]

@nehasangeetajha is already working on this issue.