*****//Precondition: Arg1 points to a complete binary tree which is also a valid  // MAX HEAP except for the root node //Postcondition: The tree pointed to by p is a valid MAX HEAP void heapify_downward(binary_tree_node*);******

**This is the code I need to use to create the heapify_downward function**

#ifndef TREEHEAP_H_ #define TREEHEAP_H_ #include "bintree.h" #include  #include  #ifdef _MSC_VER //Microsoft does not include logn in math.h, therefore, implement for MS visual ONLY double log2( double n ) { return log( n ) / log( 2 ); } #endif namespace LABTREEHEAP { template  class treeheap { public: treeheap() { root_ptr = NULL; numnodes = 0; } ~treeheap() { tree_clear(root_ptr); } //Output the tree with the head node printing LEFT JUSTIFIED and each height displaying indented void prettyprint() const; /* Precondition: the HEAP is not empty Postcondition: The MAX value in the HEAP is REMOVED and RETURNED. The tree is still a valid HEAP */ T pop(); /* Precondition: None Postcondition: The tree is still a valid MAX HEAP with the new ITEM added */ void push(const T&); private: binary_tree_node* root_ptr; size_t numnodes; /* Precondition: Arg1 points to a complete binary tree which is also a valid MAX HEAP except for the root node Postcondition: The tree pointed to by p is a valid MAX HEAP */ void heapify_downward(binary_tree_node*); /* Precondition: Arg1 points to a complete binary tree which is NOT empty. Arg2is initially set to the number of nodes-1. Postcondition: A pointer is returned pointing to the parent node of the LAST node in the complete tree */ binary_tree_node* getLastParent(binary_tree_node*,const size_t); /* Precondition: Arg1 points to a valid MAX HEAP which is NOT empty, Arg2 is initially set to the current number of nodes. Postcondition: New item is added to the tree, the tree will still be a complete tree, the tree will be reheapified as a MAX HEAP. The return value is not important to the user of this function, internally it is used as a flag to exit the heapification. */ bool completeInsert(binary_tree_node*,const T&,const size_t); }; template  void treeheap::prettyprint() const { if ( root_ptr == NULL ) std::cout << "Empty tree" << std::endl; else { std:: cout << std::endl; print(root_ptr,0); std::cout << std::endl; } } template  T treeheap::pop() { assert ( numnodes > 0 ); T poppedItem; //Pop poppedItem = root_ptr->data(); if ( numnodes == 1 ) { tree_clear(root_ptr); numnodes = 0; } else { binary_tree_node* pParent = getLastParent(root_ptr,numnodes-1); if ( pParent->right() == NULL ) { root_ptr->set_data( pParent->left()->data()); delete pParent->left(); pParent->set_left(NULL); } else { root_ptr->set_data( pParent->right()->data()); delete pParent->right(); pParent->set_right(NULL); } --numnodes; heapify_downward(root_ptr); } return poppedItem; } template  void treeheap::push(const T& item) { if ( root_ptr == NULL ) { root_ptr = new binary_tree_node(item); numnodes = 1; } else { completeInsert(root_ptr,item,numnodes); } } template  bool treeheap::completeInsert(binary_tree_node* p,const T& item,const size_t targetleaf) { //Number of possible nodes at highest depth size_t height = (size_t)log2(targetleaf+1); size_t nodesLast = (size_t)std::pow(2,height); //#Max # of leaves at this height bool reheapify = true; //By default we willl reheapify binary_tree_node* visitNode = NULL; if ( height == 1 && p->left() == NULL ) { visitNode = new binary_tree_node(item); p->set_left(visitNode); ++numnodes; } else if ( height == 1 ) { visitNode = new binary_tree_node(item); p->set_right(visitNode); ++numnodes; } else { if ( targetleaf - (size_t)std::pow(2,height) + 1 < nodesLast/2 ) { //Go Left visitNode = p->left(); reheapify = completeInsert(visitNode,item,targetleaf-std::pow(2,height-1)); } else { visitNode = p->right(); reheapify = completeInsert(visitNode,item,targetleaf-std::pow(2,height)); } } //Reheapify Upwards if ( reheapify) { if ( visitNode->data() > p->data() ) { std::swap( visitNode->data(), p->data() ); return true; } } return false; } template  binary_tree_node* treeheap::getLastParent(binary_tree_node* p,const size_t targetleaf) { //Number of possible nodes at highest depth size_t height = (size_t)log2(targetleaf+1); size_t nodesLast = pow(2,height); //#Max # of leaves at this height if ( height == 1 ) { return p; } else { if ( targetleaf - pow(2,height) + 1 < nodesLast/2 ) { return getLastParent(p->left(),targetleaf-pow(2,height-1)); } else { return getLastParent(p->right(),targetleaf-pow(2,height)); } } } } /* namespace LABTREEHEAP */ //Student implementation is contained in #include "treeheap.hpp" #endif /* TREEHEAP_H_ */

---------------------------------------------------------------------