Add Pairing Heap

[czgdp1807]

Description of the problem

Example of the problem

References/Other comments

.. [1] https://en.wikipedia.org/wiki/Pairing_heap .. [2] https://github.com/codezonediitj/pydatastructs/wiki/Plan-of-Action-for-the-Projects

[mugdhajoshi]

Can I work on this issue as part of GSSoC 2020

[czgdp1807]

Hi @mugdhajoshi This issue is reserved for RGSoC, 2020. Please see this list of GSSoC, 2020 issues.

[Pihu1998]

Hi @czgdp1807 , I am a part of RGSoC'20. Can I work on this issue?

[czgdp1807]

Hi @Pihu1998 Sure, you can start the work on this issue by proposing an API design for pairing heap. Please see the references in the description for some ideas. Feel free to ask your queries/doubts.

[Pihu1998]

Yeah, sure. :)

[din1881]

Hello, this is team bro-grammers from RGSoC '20! This API design was referenced by https://en.wikipedia.org/wiki/Pairing_heap . Please review it and get back to us.

Here is the API design in which we suggest the pairing heap would be implemented: We will have a class PairingHeap which will contain the following members: 1- data: value of current node. 2- LeftChild: reference to the left child node. 3- sibling: reference to the sibling node.

• The variables: root.

The Class will have the following methods:

• [ ] _isEmpty : A function that will check if root of the heap is null.
• [ ] find_Min : A function that returns the heap.
• [ ] merge: A function that merges two heaps, satisfying min heap condition and if one of the heaps is empty, it will return the other.
• [ ] insert: A function that inserts a node and uses the merge method.
• [ ] delete: A function that deletes the root of the heap.

[czgdp1807]

We will have a class PairingHeap which will contain the following members: 1- data: value of current node. 2- LeftChild: reference to the left child node. 3- sibling: reference to the sibling node.

Can we reuse MAryTreeNode as nodes of pairing heap because this heap is nothing but a multi way tree(refer, https://www.cise.ufl.edu/~sahni/dsaaj/enrich/c13/pairing.htm). See, https://github.com/codezonediitj/pydatastructs/blob/aebae4c801c60d0f92705d53321e222a744da307/pydatastructs/utils/misc_util.py#L109

The Class will have the following methods:

• [ ] _isEmpty : A function that will check if root of the heap is null.
• [ ] find_Min : A function that returns the heap.
• [ ] merge: A function that merges two heaps, satisfying min heap condition and if one of the heaps is empty, it will return the other.
• [ ] insert: A function that inserts a node and uses the merge method.
• [ ] delete: A function that deletes the root of the heap.

1. _isEmtpy -> is_empty
2. find_Min -> find_min

[din1881]

Okay, we'll modify the API design and get back to you. @czgdp1807

[DaliaAymanAmeen]

Here is the modified version of the API design:

1- data: value of current node. 2- key: for comparison operations. 3- Children: DynamicOneDimensionalArray.

The variables: root. The Class will have the following methods:

• [ ] is_empty: A function that will check if root of the heap is null.
• [ ] find_min: A function that returns the heap.
• [ ] merge: A function that merges two heaps, satisfying min heap condition and if one of the heaps is empty, it will return the other.
• [ ] insert: A function that inserts a node and uses the merge method.
• [ ] delete: A function that deletes the root of the heap.

[czgdp1807]

IMHO, we do not need a new kind of node. You should be able to reuse, MAryTreeNode in Pairing heap. Rest looks good. You can make a PR for this. Please do not forget to add tests(should be simple enough, I'd suggest pick them from a university lecture, like, https://www.cise.ufl.edu/~sahni/dsaaj/enrich/c13/pairing.htm) and documentation strings(follow numpy doc string style). Take your time, understand the coding style and then make a PR.