C++. Use the definition and the code for the heap developed in class and add the member function int heapRemove ()to the Heap class. The heapRemove() returns the value of the root and readjust the heap to maintain the heap property. [Hint: heapRemove() uses percolate down function]

#include  #include  using namespace std; //===================== The Node class for the Binary Search Tree ===== template class Node { public: Node(); Node(T e, Node* r, Node* l); T element; // holds the node element Node* right; Node* left; }; //======================= implementation of the constrcutors of the Node template Node::Node() { right = left = NULL; } template Node::Node(T e, Node* r, Node* l) { element = e; right = r; left = l; } //======================= Binart Searct Tree (BST) class =========== template class BTree { public: BTree() { root = NULL; } BTree(Node* rt) { root = rt; } void BSTInsert(T value); void BSTRemove(T value); Node*& getRoot() { return root; } // returns the pointer to the root Node* BSTsearch(T value); private: Node* root; // a pointer to the root of the tree }; template Node* BTree::BSTsearch(T value) { // set cur Node pointer to the tree root, traverse down the tree using cur to find the element. // Do not use the root, if you move the root the tree will be lost. //return null if element is not found Node* cur = root; while (cur != NULL) { if (value == cur->element) return cur; else if (value < cur->element) cur = cur->left; else cur = cur->right; } return NULL; } // traverse down the tree and insert at the bottom of the tree as a new leaf template void BTree::BSTInsert(T value) { Node* newNode = new Node(value, NULL, NULL); // dynamically create a node with the given value if (root == NULL) //Empty tree, fisrt node. root = newNode; else { Node* r = root; while (r != NULL) { if (value < r->element) { if (r->left == NULL) { r->left = newNode; //insert the node r = NULL; // end the loop. } else r = r->left; // keep going to the left child } else { if (r->right == NULL) { r->right = newNode; r = NULL; } else r = r->right; } } } } // recursive implementation of insert into BST ( nonmember function) template void insert(Node*& rt, T value) { Node* newNode = new Node(value, NULL, NULL); if (rt == NULL) rt = newNode; else if (value < rt->element) insert(rt->left, value); else insert(rt->right, value); } //============================== inorder traversal: Visit Left child - Visit Node - Visit right child // A recursive function ( nonmember function) template void inOrderTravel(Node* r) { if (r == NULL); // base case, do nothing here ( left - parent-right) else { inOrderTravel(r->left); std::cout << r->element << " "; inOrderTravel(r->right); } } //Three cases to consider when removing an element from a BST template void BTree::BSTRemove(T value) { Node* parent = NULL; // Need to track the parent of the node to be deleted Node* current = root; // current will point to the node to be deleted //find the node to be removed while (current != NULL && current->element != value) { if (value < current->element) { parent = current; current = current->left; } else { parent = current; current = current->right; } } if (current != NULL) // The node to be deleted is found { //Case A : the node is a leaf node if (current->left == NULL && current->right == NULL) { if (parent->right == current) parent->right = NULL; else parent->left = NULL; delete current; } //Case B: the node has two children // Must find the smalles element in the right subtree of the node, which is //found by going to the right child of the node then all the way to the left. else if (current->left != NULL && current->right != NULL) { Node* succ = current->right; // go to the right child of the node to be removed parent = current; // initialize parent node while (succ->left != NULL) // then find the smallest element in the left subtree { parent = succ; succ = succ->left; } current->element= succ->element; if (succ==current->right) // successor is the immediate right child current->right = succ->right; // else { parent->left = NULL; // skip the succ node if (succ->right != NULL) parent->right = succ->right; } delete succ; } else // Case C: Node has one child { if (root->element == value) //if the node is the root node treat differently { cout << "here "; if (root->right != NULL) root = root->right; else root = root->left; } else // a non root node with one child to be removed { if (current->left != NULL) parent->left = current->left; else parent->right = current->right; } delete current; } } } //================================ Definitions of the Heap class ======================== const int HEAPCAPACITY = 20; // max heap capacity //Heap consists of a vector to hold the elementsh template class Heap { public: Heap() { h = vector(HEAPCAPACITY); heapSize = 0; } Heap(T a[], int size); // make a heap from an array (use vector structure) void percolateUp(int nodeIndex); void percolateDown(int nodeIndex, int s); void heapify(); void heapSort(); void heapInsert(T value); void printHeap(); //T heapRemove(); private: vector h; int heapSize; }; //=======================================Heap constructor //copies the array "a" over to the heap vector. Heap property does not hold at this point template Heap::Heap(T a[], int size) { h = vector(HEAPCAPACITY); for (int i = 0; i < size; i++) h[i] = a[i]; heapSize = size; //set the heap size } //============================================ heap insert //inserts an elemengt in the last loaction and percolates the element up template void Heap::heapInsert(T value) { if (heapSize < HEAPCAPACITY) { h[heapSize] = value; heapSize += 1; } percolateUp(heapSize - 1); } //======================================== Percolate up //Compare element with its parent value, if larger swap with partent //repeat if needed template void Heap::percolateUp(int nodeIndex) { int parentIndex; while (nodeIndex > 0) { parentIndex = (nodeIndex - 1) / 2; if (h[nodeIndex] <= h[parentIndex]) // compare with parent return; else { swap(h[nodeIndex], h[parentIndex]); nodeIndex = parentIndex; } } } //========================================= Percolate Down=============== //Compare node value with its children and swap with the larger of the two children template void Heap::percolateDown(int nodeIndex, int s) //s is the size of the vector { int leftChildIndex = 2 * nodeIndex + 1; T value = h[nodeIndex]; while (leftChildIndex <= s) // make sure the right child is not out of range { T maxValue = value; int maxIndex = -1; for (int i = 0; i < 2 && i + leftChildIndex < s; i++) //select the larger of the two children { if (h[i + leftChildIndex] > maxValue) { maxValue = h[i + leftChildIndex]; maxIndex = i + leftChildIndex; } } if (value == maxValue) //compare node value with the larger of the two children return; else { //swap if necessary and continue down the tree. swap(h[nodeIndex], h[maxIndex]); nodeIndex = maxIndex; leftChildIndex = 2 * nodeIndex + 1; } } } //====================================== heapify //Turns a vector into a a Heap, after heapify the elements of the vector //satisfy the heap property template void Heap::heapify() { //start from the middle of the list apply percolate down to the elements and //move backward up to the root for (int i = (heapSize / 2) - 1; i >= 0; i--) percolateDown(i, heapSize); } template void Heap::printHeap() { cout << "heap content =====> "; for (int i = 0; i < heapSize; i++) cout << h[i] << " "; cout << endl; } //=========================================heap Sort //After heap sort the heap elements will be in sorted order. // if max.heap sorts in an increasing order // if min.Heap sorts in a decreasing order template void Heap::heapSort() { for (int i = heapSize - 1; i > 0; i--) { swap(h[0], h[i]); percolateDown(0, i); } } int main() { //Testing the Binary Search Tree BTree bst; //insert few numbers into the BST. bst.BSTInsert(300); bst.BSTInsert(775); bst.BSTInsert(100); // 100 300 775 bst.BSTInsert(25); bst.BSTInsert(750); bst.BSTInsert(925); bst.BSTInsert(11); bst.BSTInsert(201); bst.BSTInsert(500);// BST with 9 nodes //inOredrTravel receives the root node and traverses the tree in order inOrderTravel(bst.getRoot()); cout << endl; // do additional insert and remove to verify proper working of the BST bst.BSTInsert(54); bst.BSTInsert(5); inOrderTravel(bst.getRoot()); cout << endl; bst.BSTRemove(11); //A node with one child inOrderTravel(bst.getRoot()); cout << endl; bst.BSTInsert(800); bst.BSTInsert(790); bst.BSTInsert(799); inOrderTravel(bst.getRoot()); cout << endl; bst.BSTRemove(775); inOrderTravel(bst.getRoot()); cout << endl; cout << bst.BSTsearch(300)->element << endl; bst.BSTRemove(300); inOrderTravel(bst.getRoot()); cout << endl; // Heap has two constrcutors, one creates an empty heap and the other // receives an array of elements with its size to initialize a heap /* cout << "========================== HEAP ============================== "; int a[10] = { 4, 2, 8, 9, 1, 6, 8, 12, 11, 15 }; Heap h(a, 10); h.printHeap(); // at this point the heap elements do not satisfy the heap property h.heapify(); // apply heapify to turn the array into a heap h.printHeap(); h.heapInsert(80); h.printHeap(); h.heapSort(); h.printHeap(); //create an empty heap and insert elements in it Heap h2; h2.heapInsert('D'); h2.heapInsert('A'); h2.heapInsert('C'); h2.heapInsert('E'); h2.heapInsert('B'); h2.printHeap(); h2.heapSort(); h2.printHeap(); */ return 0; }