For this computer assignment, you are to write a C++ program to sort numbers using the heapsort technique. Your program first builds a heap structure for the numbers. Then, it retrieves these numbers from the heap in a certain order and prints them out on stdout.

The source file assignment7.cc is partially implemented and contains the complete implementation of the main function.

Add and implement the following functions in this source file

-void build_heap ( vector < int >& v, int heap_size, bool (*compar)(int, int) ): This function constructs a heap with heap_size elements in the vector v. Pay attention that elements start at position 1 (position 0 is wasted and ignored) in the vector. compar is a function pointer (predicate) to compare two integers. build_heap will invoke heapify specified below

-void heapify( vector < int >& v, int heap_size, int r, bool (*compar)(int, int) ): This function heapifies a tree at the root position r, assuming rs two sub-trees are already heaps. heap_size specifies the size of the whole heap contained by the vector (the heap starts at position 1 of the vector). This function uses the function pointer compar to compare two elements. This function can be implemented recursively.

-bool less_than ( int e1, int e2 ): This function compares two integers and returns true if e1 is less than e2. Otherwise it returns false. When this function is used as predicate in build_heap, a min heap will be constructed.

-bool greater_than ( int e1, int e2 ): This function compares two integers and returns true if e1 is greater than e2. Otherwise it returns false. When this function is used as predicate in build_heap, a max heap will be constructed.

-void heap_sort ( vector < int >& v, int heap_size, bool (*compar)(int, int) ): This function implement the heap sort algorithm. At beginning the vector v contains a heap. At the end of this function, vector v contains sorted elements. Similar to build_heap, there is a predicate in the parameter list to specify how to compare two elements. If less_than is passed in as argument here, the results are in ascending order. If greater_than is used, the results are in descending order. heap_sort will invoke extract_heap specified below. You can use the STL algorithm reverse if necessary

-int extract_heap ( vector < int >& v, int& heap_size, bool (*compar)(int, int) ): This function extracts the root of the heap recorded in v, fills the root with the last element of the current heap, updates heap_size, heapifies at the root, and returns the old root value. This function will invoke heapify specified above.

-void print_vector ( vector < int >& v, int pos, int size ): This function displays size number of elements contained in vector v starting at position pos. It shows 8 elements per line. Each item occupies 5 spaces.

********notes********

-Please implement the algorithms to build the heap and sort by heapsort. Do not invoke the STL algorithms make_heap or heap_sort.

-Please pay extra attention that in this assignment vectors elements start at position 1 (instead of position 0) unless otherwise specified.

-Include any necessary headers and add necessary global constants.

-You are not allowed to use any I/O functions from the C library, such as scanf or printf. Instead, use the I/O functions from the C++ library, such as cin or cout

-In the final version of your assignment, you are not supposed to change existing code, including the main method, provided to you in the original source file assginment7.cc.

- please do not change the name of the file.

***************************assignment7.cc*******************

const int HEAP_SIZE = 50;

int main(int argc, char** argv) { // ------- creating input vector -------------- vector v; v.push_back(-1000000); // first element is fake for (int i=1; i<=HEAP_SIZE; i++) v.push_back( i ); random_shuffle( v.begin()+1, v.begin()+HEAP_SIZE+1 );

cout << " Current input numbers: " << endl; print_vector( v, 1, HEAP_SIZE );

// ------- testing min heap ------------------ cout << " Building a min heap..." << endl; build_heap(v, HEAP_SIZE, less_than); cout << "Min heap: " << endl; print_vector( v, 1, HEAP_SIZE ); heap_sort( v, HEAP_SIZE, less_than);

cout << "Heap sort result (in ascending order): " << endl; print_vector( v, 1, HEAP_SIZE );

// ------- testing max heap ------------------ cout << " Building a max heap..." << endl; build_heap(v, HEAP_SIZE, greater_than); cout << "Max heap: " << endl; print_vector( v, 1, HEAP_SIZE ); heap_sort( v, HEAP_SIZE, greater_than); cout << "Heap sort result (in descending order): " << endl;

print_vector( v, 1, HEAP_SIZE );

return 0; }

*****************outout************* (this is the way the out put is suppose to look like )

Current input numbers: 5 29 12 16 25 36 18 37 27 49 34 40 20 3 48 50 26 19 33 41 6 22 8 13 15 43 28 7 46 45 31 39 14 38 4 17 30 44 10 23 9 24 21 35 2 11 32 1 47 42

Building a min heap... Min heap: 1 2 3 4 6 12 5 14 10 9 8 13 20 7 31 16 26 17 27 23 21 22 11 36 15 43 28 18 46 45 48 39 50 38 37 19 30 44 33 29 41 24 49 35 34 25 32 40 47 42

Heap sort result (in ascending order): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Building a max heap... Max heap:

50 47 49 39 46 48 31 35 38 43 45 25 27 29 30 33 34 37 19 41 42 44 23 24 12 26 13 28 14 7 15 32 16 8 17 36 18 9 4 40 20 10 21 2 22 11 5 6 3 1

Heap sort result (in descending order): 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1