//Data structures using c++ please Replace the arrays with binary search trees #

Question

//Data structures using c++ please

Replace the arrays with binary search trees

#include <algorithm>
#include <array>
#include <ctime>
#include <iterator>
#include <iostream>
#include <random>
#include <string>

using namespace std;
const size_t array_size = 16;

template
void randomIntFill(array& elts, default_random_engine& e, uniform_int_distribution& u)
{
   for(Type& elt : elts)
       elt = u(e);
}
template
void show(array elts, ostream& sout = cout)
{
   for(Type elt : elts)
       sout << elt << ' ';
}
template
void heapify(array& elts, unsigned parent_index, unsigned last_heap_index)
{
   unsigned left_child_index = 2 * parent_index + 1;
   if (left_child_index <= last_heap_index)
   {
       unsigned right_child_index = left_child_index + 1;
       unsigned max_child_index = left_child_index;
       if (right_child_index <= last_heap_index && elts[max_child_index] < elts[right_child_index])
           max_child_index = right_child_index;
       if (elts[parent_index] < elts[max_child_index])
       {
           swap(elts[parent_index], elts[max_child_index]);
           heapify(elts, max_child_index, last_heap_index);
       }
   }
}
template
void buildHeap(array& elts)
{
   for (int i = elts.max_size() - 1; i >= 0; i--)
       heapify(elts, i, elts.max_size() - 1);
}
template
void heapSort(array & elts)
{
   buildHeap(elts);
   for (unsigned i = elts.max_size() - 1; i > 0; i--)
   {
       swap(elts[0], elts[i]);
       heapify(elts, 0, i - 1);
   }
}
int main()
{
   const unsigned upper_bound = 99;
   const unsigned lower_bound = 10;
   unsigned seed = 0;
   default_random_engine e(seed);
   uniform_int_distribution u(lower_bound, upper_bound);
   array a;
  
   randomIntFill(a, e, u);
   show(a); cout << endl;
   heapSort(a);
   show(a); cout << endl;
   system("pause");
   return 0;
}

Explanation / Answer

#include <algorithm>
#include <array>
#include <ctime>
#include <iterator>
#include <iostream>
#include <random>
#include <string>

using namespace std;
const size_t array_size = 16;

template
void randomIntFill(array& elts, default_random_engine& e, uniform_int_distribution& u)
{
   for(Type& elt : elts)
       elt = u(e);
}
template
void show(array elts, ostream& sout = cout)
{
   for(Type elt : elts)
       sout << elt << ' ';
}
template
void heapify(array& elts, unsigned parent_index, unsigned last_heap_index)
{
   unsigned left_child_index = 2 * parent_index + 1;
   if (left_child_index <= last_heap_index)
   {
       unsigned right_child_index = left_child_index + 1;
       unsigned max_child_index = left_child_index;
       if (right_child_index <= last_heap_index && elts[max_child_index] < elts[right_child_index])
           max_child_index = right_child_index;
       if (elts[parent_index] < elts[max_child_index])
       {
           swap(elts[parent_index], elts[max_child_index]);
           heapify(elts, max_child_index, last_heap_index);
       }
   }
}
template
void buildHeap(array& elts)
{
   for (int i = elts.max_size() - 1; i >= 0; i--)
       heapify(elts, i, elts.max_size() - 1);
}
template
void heapSort(array & elts)
{
   buildHeap(elts);
   for (unsigned i = elts.max_size() - 1; i > 0; i--)
   {
       swap(elts[0], elts[i]);
       heapify(elts, 0, i - 1);
   }
}
int main()
{
   const unsigned upper_bound = 99;
   const unsigned lower_bound = 10;
   unsigned seed = 0;
   default_random_engine e(seed);
   uniform_int_distribution u(lower_bound, upper_bound);
   array a;
  
   randomIntFill(a, e, u);
   show(a); cout << endl;
   heapSort(a);
   show(a); cout << endl;
   system("pause");
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.