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. Used the functions that are provided.

bool less_than = min heap

bool greater_than= max heap

const int HEAP_SIZE = 50;

void build_heap(vector < int >& v, int heap_size, bool(*compar)(int, int)); //constructs a heap with heap_size elements in the vector v. Pay attention that elements start at //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)); //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)); //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

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.

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; }