Implement downHeap(Node *n) for a min heap implemented as an ordinary binary tree with an integer member variable "value" and left and right child pointers. Any node might have only a left child, only a right child, both, or neither.

The starter code below defines a class called "Node" that has two child pointers ("left" , "right") and an integer "value" member variable. There is also a constructor Node(int val) that initializes the children to nullptr and the node's value to val.

Your job is to implement the procedure "downHeap(Node *n)" . The procedure should assume that n->left is the root of a min heap subtree (or nullptr) and the same for n->right. The value at Node *n (specifically n->value) might not be less than the values in its left subtree and in its right subtree, and so the tree with Node *n as its root might not be a min heap (even though its left subtree and right subtree are both min heaps). Your code should modify the tree rooted at Node *n so it is a min heap. You do not need to balance the tree or turn it into a complete tree. You only need to ensure that the tree satisfies the min heap property:

For a min heap, it is okay for a node's value to be equal to one or both of its children, but the node's value must not be greater than either of its children.

class Node { public: int value; Node *left, *right; Node(int val = 0) { value = val; left = right = nullptr; } ~Node() { delete left; left = nullptr; delete right; right = nullptr; } };

This function has also previously been defined for you:

void printTreeVertical(const Node* n);

You can use it to print a verbose, vertical diagram of a tree rooted at n. In this vertical format, a left child is shown above a right child in the same column. If no child exists, [null] is displayed.

*/

void downHeap(Node *n)

{ }

// You can also use this compact printing function for debugging. void printTree(Node *n) { if (!n) return; std::cout << n->value << "("; printTree(n->left); std::cout << ")("; printTree(n->right); std::cout << ")"; }

int main() { Node *n = new Node(100); n->left = new Node(1); n->right = new Node(2); n->right->left = new Node(3); n->right->right = new Node(4); n->right->right->right = new Node(5);

downHeap(n);

std::cout << "Compact printout:" << std::endl; printTree(n); std::cout << std::endl << "Vertical printout:" << std::endl; printTreeVertical(n);

delete n; n = nullptr;

return 0; }