c$++$ please In the Heap Exercise an array was used to construct a minheap and maxheap. Convert your Heap to a Treap. A Treap is a node pointer version of the heap$$s internal array. Replace the vector in the Heap with: Node$*$ Root $=$ new Node$($N$)$ where N is the numeric value for the Root.

Change Left Index Calculation: $2*$index $+1$ to a $<<$ Leftptr of the Node

Change Right Index Calculcation: $2*$index$+2$ to a $>>$ RightPtr of the Node

A Treap $($Tree $+$ Heap$)$ is a form of binary search tree data structure that maintains the heap properties and allows binary searches among the keys.

Node Definition:

template

class node $\{$

T tdata;

node $*$pleft$,*$pright;

public:

node$($T t$)\{$ tdata $=$ t; pleft $=$ NULL; pright $=$ NULL; $\}$

T data$()\{$ return tdata; $\}$

node$*$ left$()\{$ return pleft; $\}$

void setleft$($node$*$ pn$)\{$ pleft $=$ pn; $\}$

node$*$ right$()\{$ return pright; $\}$

void setright$($node$*$ pn$)\{$ pright $=$ pn; $\}\}$;