Rewrite the heap sort function as a descending order sort. Do not simply sort items in ascending order and then reverse the order of the array elements.

Write a program to test your function.

DATA STRUCTURE/ C++

array list type.h

#ifndef H_arrayListType #define H_arrayListType #include #include using namespace std; template class arrayListType { public: int findKthLargest(vector& v, int kth); void build(vector& v); void heapify(vector& v, int low, int high); const arrayListType& operator= (const arrayListType&); //Overloads the assignment operator bool isEmpty(); //Function to determine whether the list is empty //Postcondition: Returns true if the list is empty; // otherwise, returns false. bool isFull(); //Function to determine whether the list is full. //Postcondition: Returns true if the list is full; // otherwise, returns false. int listSize(); //Function to determine the number of elements in the list //Postcondition: Returns the value of length. int maxListSize(); //Function to determine the size of the list. //Postcondition: Returns the value of maxSize. void print() const; //Function to output the elements of the list //Postcondition: Elements of the list are output on the // standard output device. bool isItemAtEqual(int location, const elemType& item); //Function to determine whether the item is the same //as the item in the list at the position specified by //Postcondition: Returns true if the list[location] // is the same as the item; otherwise, // returns false. void insertAt(int location, const elemType& insertItem); //Function to insert an item in the list at the //position specified by location. The item to be inserted //is passed as a parameter to the function. //Postcondition: Starting at location, the elements of the // list are shifted down, list[location] = insertItem;, // and length++;. If the list is full or location is // out of range, an appropriate message is displayed. void insertEnd(const elemType& insertItem); //Function to insert an item at the end of the list. //The parameter insertItem specifies the item to be inserted. //Postcondition: list[length] = insertItem; and length++; // If the list is full, an appropriate message is // displayed. void removeAt(int location); //Function to remove the item from the list at the //position specified by location //Postcondition: The list element at list[location] is removed // and length is decremented by 1. If location is out of // range,an appropriate message is displayed. void retrieveAt(int location, elemType& retItem); //Function to retrieve the element from the list at the //position specified by location. //Postcondition: retItem = list[location] // If location is out of range, an appropriate message is // displayed. void replaceAt(int location, const elemType& repItem); //Function to replace the elements in the list at the //position specified by location. The item to be replaced //is specified by the parameter repItem. //Postcondition: list[location] = repItem // If location is out of range, an appropriate message is // displayed. void clearList(); //Function to remove all the elements from the list. //After this operation, the size of the list is zero. //Postcondition: length = 0; int seqSearch(const elemType& item); //Function to search the list for a given item. //Postcondition: If the item is found, returns the location // in the array where the item is found; otherwise, // returns -1. void insert(const elemType& insertItem); //Function to insert the item specified by the parameter //insertItem at the end of the list. However, first the //list is searched to see whether the item to be inserted //is already in the list. //Postcondition: list[length] = insertItem and length++ // If the item is already in the list or the list // is full, an appropriate message is displayed. void remove(const elemType& removeItem); //Function to remove an item from the list. The parameter //removeItem specifies the item to be removed. //Postcondition: If removeItem is found in the list, // it is removed from the list and length is // decremented by one. void selectionSort(); //Function to sort array list using selection sort algorithm void insertionSort(); //Function to sort array list using selection sort algorithm void intervalInsertionSort(int firstPosition, int increment); //Function to partially sort array using interval insertion sort algorithm void shellSort(); //Function to sort array list using shell sort algorithm void quickSort(); //Function to sort array list using quick sort algorithm void heapSort(); //Function to sort array list using heap sort algorithm arrayListType(int size = 100); //constructor //Creates an array of the size specified by the //parameter size. The default array size is 100. //Postcondition: The list points to the array, length = 0, // and maxSize = size arrayListType(const arrayListType& otherList); //copy constructor ~arrayListType(); //destructor //Deallocates the memory occupied by the array. protected: elemType *list; //array to hold the list elements int length; //to store the length of the list int maxSize; //to store the maximum size of the list void swap(int first, int second); int minLocation(int first, int last); private: int partition(int first, int last); void recQuickSort(int first, int last); void buildHeap(); void heapify(int low, int high); }; template void arrayListType::build(vector& v) { int temp; int n = v.size(); for (int i = n / 2 - 1; i >= 0; i--) heapify(v, n, i); for (int i = n - 1; i >= 0; i--) { // Move current root to end temp = v[0]; v[0] = v[i]; v[i] = temp;

// call max heapify on the reduced heap heapify(v, i, 0); } } template void arrayListType::heapify(vector& v, int low, int high) { int largest = low; // Initialize largest as root int l = 2 * low + 1; // left = 2*i + 1 int r = 2 * low + 2; // right = 2*i + 2 int temp;

// If left child is larger than root if (l < high&& v[l] > v[largest]) largest = l;

// If right child is larger than largest so far if (r < high && v[r] > v[largest]) largest = r;

// If largest is not root if (largest != low) { //swap(arr[i], arr[largest]); temp = v[low]; v[low] = v[largest]; v[largest] = temp;

// Recursively heapify the affected sub-tree heapify(v, high, largest); } } template int arrayListType::findKthLargest(vector& v, int kth) { //build(v); cout << " The " << kth << " element is -->" << v[kth - 1] << endl; return kth; } template bool arrayListType::isEmpty() { return (length == 0); } template bool arrayListType::isFull() { return (length == maxSize); } template int arrayListType::listSize() { return length; } template int arrayListType::maxListSize() { return maxSize; } template void arrayListType::print() const { for (int i = 0; i < length; i++) cout << list[i] << " "; cout << endl; } template bool arrayListType::isItemAtEqual (int location, const elemType& item) { return(list[location] == item); } template void arrayListType::insertAt (int location, const elemType& insertItem) { if (location < 0 || location >= maxSize) cerr << "The position of the item to be inserted " << "is out of range" << endl; else if (length >= maxSize) //list is full cerr << "Cannot insert in a full list" << endl; else { for (int i = length; i > location; i--) list[i] = list[i - 1]; //move the elements down list[location] = insertItem; //insert the item at the //specified position length++; //increment the length } } //end insertAt template void arrayListType::insertEnd(const elemType& insertItem) { if (length >= maxSize) //the list is full cerr << "Cannot insert in a full list" << endl; else { list[length] = insertItem; //insert the item at the end length++; //increment the length } } //end insertEnd template void arrayListType::removeAt(int location) { if (location < 0 || location >= length) cerr << "The location of the item to be removed " << "is out of range" << endl; else { for (int i = location; i < length - 1; i++) list[i] = list[i + 1]; length--; } } //end removeAt template void arrayListType::retrieveAt (int location, elemType& retItem) { if (location < 0 || location >= length) cerr << "The location of the item to be retrieved is " << "out of range." << endl; else retItem = list[location]; } //end retrieveAt template void arrayListType::replaceAt (int location, const elemType& repItem) { if (location < 0 || location >= length) cerr << "The location of the item to be replaced is " << "out of range." << endl; else list[location] = repItem; } //end replaceAt template void arrayListType::clearList() { length = 0; } //end clearList template int arrayListType::seqSearch(const elemType& item) { int loc; bool found = false; for (loc = 0; loc < length; loc++) if (list[loc] == item) { found = true; break; } if (found) return loc; else return -1; } //end seqSearch template void arrayListType::insert(const elemType& insertItem) { int loc; if (length == 0) //list is empty list[length++] = insertItem; //insert the item and //increment the length else if (length == maxSize) cerr << "Cannot insert in a full list." << endl; else { loc = seqSearch(insertItem); if (loc == -1) //the item to be inserted //does not exist in the list list[length++] = insertItem; else cerr << "the item to be inserted is already in " << "the list. No duplicates are allowed." << endl; } } //end insert template void arrayListType::remove(const elemType& removeItem) { int loc; if (length == 0) cerr << "Cannot delete from an empty list." << endl; else { loc = seqSearch(removeItem); if (loc != -1) removeAt(loc); else cout << "The item to be deleted is not in the list." << endl; } } //end remove template arrayListType::arrayListType(int size) { if (size < 0) { cerr << "The array size must be positive. Creating " << "an array of size 100. " << endl; maxSize = 100; } else maxSize = size; length = 0; list = new elemType[maxSize]; assert(list != NULL); } template arrayListType::~arrayListType() { delete[] list; } template arrayListType::arrayListType (const arrayListType& otherList) { maxSize = otherList.maxSize; length = otherList.length; list = new elemType[maxSize]; //create the array assert(list != NULL); //terminate if unable to allocate //memory space for (int j = 0; j < length; j++) //copy otherList list[j] = otherList.list[j]; } //end copy constructor template const arrayListType& arrayListType::operator= (const arrayListType& otherList) { if (this != &otherList) //avoid self-assignment { delete[] list; maxSize = otherList.maxSize; length = otherList.length; list = new elemType[maxSize]; //create the array assert(list != NULL); //if unable to allocate memory //space, terminate the program for (int i = 0; i < length; i++) list[i] = otherList.list[i]; } return *this; } template void arrayListType::selectionSort() { int minIndex; for (int loc = 0; loc < length - 1; loc++) { minIndex = minLocation(loc, length - 1); swap(loc, minIndex); } } //end selectionSort template void arrayListType::insertionSort() { int firstOutOfOrder, location; elemType temp; for (firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++) if (list[firstOutOfOrder] < list[firstOutOfOrder - 1]) { temp = list[firstOutOfOrder]; location = firstOutOfOrder; do { list[location] = list[location - 1]; location--; } while (location > 0 && list[location - 1] > temp); list[location] = temp; } } //end insertionSort template void arrayListType::intervalInsertionSort(int start, int increment) { int firstOutOfOrder, location; elemType temp; for (firstOutOfOrder = start + increment; firstOutOfOrder < length; firstOutOfOrder += increment) if (list[firstOutOfOrder] < list[firstOutOfOrder - increment]) { temp = list[firstOutOfOrder]; location = firstOutOfOrder; do { list[location] = list[location - increment]; location -= increment; } while (location > start && list[location - increment] > temp); list[location] = temp; } } //end insertvalInsertionSort template void arrayListType::shellSort() { int inc; for (inc = 1; inc < (length - 1) / 9; inc = 3 * inc + 1) ; do { for (int begin = 0; begin < inc; begin++) { intervalInsertionSort(begin, inc); print(); } inc = inc / 3; } while (inc > 0); } //end shellSort template void arrayListType::quickSort() { recQuickSort(0, length - 1); } template void arrayListType::recQuickSort(int first, int last) { int pivotLocation; if (first < last) { pivotLocation = partition(first, last); recQuickSort(first, pivotLocation - 1); recQuickSort(pivotLocation + 1, last); } } template int arrayListType::partition(int first, int last) { elemType pivot; int index, smallIndex; swap(first, (last + first) / 2); pivot = list[first]; smallIndex = first; for (index = first + 1; index <= last; index++) if (list[index] < pivot) { smallIndex++; swap(smallIndex, index); } swap(first, smallIndex); return smallIndex; } template void arrayListType::heapSort() { elemType temp; buildHeap(); for (int lastOutOfOrder = length - 1; lastOutOfOrder >= 0; lastOutOfOrder--) { temp = list[lastOutOfOrder]; list[lastOutOfOrder] = list[0]; list[0] = temp; heapify(0, lastOutOfOrder - 1); } } template void arrayListType::buildHeap() { for (int index = length / 2 - 1; index >= 0; index++) heapify(index, length - 1); } template void arrayListType::heapify(int low, int high) { int largeIndex = 2 * high + 1; //index of left child elemType temp = list[low]; //make copy of root node of subtree while (largeIndex <= low) { if (largeIndex < low) if (list[largeIndex] < list[largeIndex + 1]) largeIndex = largeIndex + 1; if (temp > list[largeIndex]) //subtree is already in a heap break; else { list[low] = list[largeIndex]; //move the larger child to the root high = largeIndex; //go to the subtree to restore the heap largeIndex = 2 * low + 1; } } list[high] = temp; //insert temp into the tree, that is the list } //end heapify template int arrayListType::minLocation(int first, int last) { int minIndex; minIndex = last; for (int loc = last + 1; loc <= first; loc++) if (list[loc] < list[minIndex]) minIndex = loc; return minIndex; } //end minLocation template void arrayListType::swap(int first, int second) { elemType temp; temp = list[second]; list[second] = list[first]; list[first] = temp; }//end swap #endif

DATA STRUCTURE/C++

Rewrite the heap sort function as a descending order sort. Do not simply sort items in ascending order and then reverse the order of the array elements.

Write a program to test your function.

heres the header and the source

arrayListType.h

source.cpp

#include #include #include #include #include "arrayListType.h" #include using namespace std; int main() { vector data; const unsigned upper_bound = 99; const unsigned lower_bound = 10; const int length = 8; default_random_engine e; unsigned seed = static_cast(time(NULL)); e.seed(seed); uniform_int_distribution u(lower_bound, upper_bound); arrayListType al(16); while (al.listSize() < al.maxListSize()) { al.insert(u(e)); al.print(); data.push_back(u(e)); } cout << "---" << endl; al.heapSort(); //al.selectionSort(); //al.print(); //al.quickSort();

al.print(); cout << "The vector elements are :-->" << endl; for (int i = 0; i { cout << data[i] << " "; } al.build(data); cout << endl << "The vector elements after heapsort:-->" << endl; for (int i = 0; i { cout << data[i] << " "; } al.findKthLargest(data, 2); cout << endl; system("pause"); return 0; }