Add Cartesian tree

[ajaynair710]

Description of the problem

Example of the problem

References/Other comments

[czgdp1807]

Thanks.
Are you participating through GSSoC, 2020?
For further steps, please come up with an API design for Cartesian tree

[ajaynair710]

Yes, I am participating in GSSoC

[Disha5harma]

@czgdp1807 Is this issue still available?

[czgdp1807]

@Disha5harma
Yes. Please start by API design and comment it below.

[Disha5harma]

Can you please tell me what we have to do in API design? Like in PR we have to add code only right? Actually I am new to open source contribution, please help.

…

On Thu, Mar 12, 2020 at 7:44 PM Gagandeep Singh ***@***.***> wrote: Yes. Please start by API design and comment it below. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#106 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AKOT7E7QTLVGIBSZOCZ3WKLRHDU2XANCNFSM4K7BJIYA> .

[czgdp1807]

Can you please tell me what we have to do in API design?

In API design you have to find an appropriate class prototype. It is basically how you call functions or methods of a class. See, #142 (comment) for API design of disjoint set data structure. Something similar is to be done for Cartesian trees.

[Disha5harma]

Okay,I will do it.Thanks.

…

On Fri, Mar 13, 2020 at 12:52 AM Gagandeep Singh ***@***.***> wrote: Can you please tell me what we have to do in API design? In API design you have to find an appropriate class prototype. It is basically how you call functions or methods of a class. See, #142 (comment) <#142 (comment)> for API design of disjoint set data structure. Something similar is to be done for Cartesian trees. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#106 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AKOT7E2U5IXGO4ZQZSFXCKTRHEY67ANCNFSM4K7BJIYA> .

[Disha5harma]

Following could be the API design for this problem-
node
This class will represent the notion of cartesian tree with respect to the above data structure.
Attributes

• data-stores any valid value
• left-represents left child
• right-represents right child

cartesian_tree
This class will create cartesian tree and perform operations
Attributes

• parent-to hold the index of parent of each number in the input array (arr)
• leftchild-to hold the index of left-child of each number in the input array (arr)
• rightchild-to hold the index of right-child of each number in the input array (arr)

Methods
1.create_tree(arr)-for building the cartesian tree according to sequence
2.create_helper(root,arr,parent,leftchild,rightchild)-helper function to recursively create subtree under given root
3.sort_using_cartesian(root)-helps to in sorting given arr using cartesian tree and priority queue
PriorityQueue
Implementing priority queue
Attributes

• data-valid value
• queue-list of data/pointers to data can be stored through this
• ele-valid data/pointers to data can be stored through this

Methods

1. isEmpty-checks if the queue is empty
2. insert(data)-inserts element in queue
3. delete-pop function for queue

Kindly check if this API design works.

[czgdp1807]

node
This class will represent the notion of cartesian tree with respect to the above data structure.
Attributes

• data-stores any valid value
• left-represents left child
• right-represents right child

There is already a TreeNode class which can be used for the above purpose.

cartesian_tree
This class will create cartesian tree and perform operations
Attributes

• parent-to hold the index of parent of each number in the input array (arr)
• leftchild-to hold the index of left-child of each number in the input array (arr)
• rightchild-to hold the index of right-child of each number in the input array (arr)

Methods
1.create_tree(arr)-for building the cartesian tree according to sequence
2.create_helper(root,arr,parent,leftchild,rightchild)-helper function to recursively create subtree under given root
3.sort_using_cartesian(root)-helps to in sorting given arr using cartesian tree and priority queue

Can we make these similar to the existing binary trees? Refer, https://github.com/codezonediitj/pydatastructs/blob/master/pydatastructs/trees/binary_trees.py

PriorityQueue
Implementing priority queue
Attributes

• data-valid value
• queue-list of data/pointers to data can be stored through this
• ele-valid data/pointers to data can be stored through this

Methods

1. isEmpty-checks if the queue is empty
2. insert(data)-inserts element in queue
3. delete-pop function for queue

See, #132 (comment)

[Disha5harma]

Can we make these similar to the existing binary trees? Refer, https://github.com/codezonediitj/pydatastructs/blob/master/pydatastructs/trees/binary_trees.py

Sir, I think all methods similar to this can't be implemented on cartesian tree and for rest I am working.If I am wrong then pls guide.