Add m-ary heap

[prshnt19]

Description of the problem

Currently, the package does not have m-ary heap (a generalization of the binary heap).

Example of the problem

References/Other comments

https://www.geeksforgeeks.org/k-ary-heap/

[czgdp1807]

Please provide a more reliable reference, for example Wikipedia or research paper and discuss use cases and APIs on the basis of it.
Thanks.

[prshnt19]

Reference

https://en.wikipedia.org/wiki/D-ary_heap

Use Cases

m-ary heap when used in the implementation of priority queue allows faster decrease key operation as compared to binary heap ( O(log2n)) for binary heap vs O(logmn) for m-ary heap). Nevertheless, it causes the complexity of extractMin() operation to increase to O(m log mn) as compared to the complexity of O(log2n) when using binary heaps for priority queue. This allows m-ary heap to be more efficient in algorithms where decrease priority operations are more common than extractMin() operation.Example: Dijkstra’s algorithm for single source shortest path and Prim’s algorithm for minimum spanning tree

m-ary heap has better memory cache behaviour than a binary heap which allows them to run more quickly in practice, although it has a larger worst case running time of both extractMin() and delete() operation (both being O(m log mn) ).

APIs

buildHeap() - Builds a heap from an input array.
insert() - Inserting a node into the heap
heapify() - Used to maintain heap property.
extract() - Extracting the root node.

[czgdp1807]

The above API can be modified so that it remains along the lines of current BinaryHeap. See, https://github.com/codezonediitj/pydatastructs/blob/master/pydatastructs/trees/heaps.py#L17
Please provide the function/method prototype with the arguments which will be needed.
IMO, we should allow pointers based implementation instead of array based implementation as it will be really difficult to describe the indices of the N-childs. https://github.com/codezonediitj/pydatastructs/blob/master/pydatastructs/utils/misc_util.py#L53 can be used represent nodes of m-ary trees, heaps with different alias names for each of the data structure.

[prshnt19]

The above API can be modified so that it remains along the lines of current BinaryHeap. The current implementation of BinaryHeap uses both pointers and array-based implementation. I can extend that for M-ary heap. Can you suggest a better Class Name for MAryHeap. BinomialTreeNode is a better alternative for nodes of m-ary heap

[czgdp1807]

IMO, using arrays is a safer option. Pointer based implementation makes the maintenance of code difficult. Though, BinomialHeap is using pointers, making changes to that will be a bit difficult. I would like M-ary heaps to use array based implementation as they are closer to BinaryHeap and not BinmoialHeap. A node for M-Ary heap can have an array of children indices. A new class for such nodes can be created.

[czgdp1807]

This also suggests array data structure as a support for the proposed type of heaps.

Thus, the parent of the item at position i (for any i > 0) is the item at position ⌊(i − 1)/d⌋ and its children are the items at positions di + 1 through di + d.

The above property can make it easy to add array implementation without creating a new class for nodes of DHeap. We can just use TreeNode as is the case with current BinaryHeap. I would prefer this method.