C++ Heap sort

modify all the funtions in the code given to use a template.

Heres what a Swap header looks like that uses a template:

template

void Swap(T * elements, int x, int y)

Demonstrate that the template works with something other than an int array.

#include "stdafx.h"

#include

using namespace std;

void listArr(int * arr, int start, int end);

void reHeapDown(int * elements, int root, int bottom);

void Swap(int * elements, int x, int y);

void heapSort(int * elements, int start, int end);

int main() { /* consider the situation where the top of the heap was removed and the right most child on the lowest leveel replaced it */

int heap[6] = { 2, 8, 9, 5, 3, 4 }; cout << "Listing semi-heap "; listArr(heap, 0, 5);

cout << "Try reHeap "; reHeapDown(heap, 0, 5); listArr(heap, 0, 5);

cout << "Sorting using Heap Sort "; heapSort(heap, 0, 5); listArr(heap, 0, 5);

return 0; }

/** @pre int array @post array displayed @param arr address of an int array @param start int starting point of array @param end int ending point of array */ void listArr(int * arr, int start, int end) { if (start > end) //Invalid input return; cout << arr[start]; if (start + 1 <= end) for (int i = start + 1; i <= end; ++i) cout << " " << arr[i]; cout << " "; }

/** @pre integer array @post array displayed @param arr address of an int array @param start int starting point of array @param end int ending point of array

reHeapDown(heap, root, bottom) if heap element[root] is not a leaf Set maxChild to index of child with larger value if heap element[root] < heal element[maxChild] Swap(heap elements[root], heap lements[maxChild] reHeapDown(heap, maxChild, bottom */ void reHeapDown(int * elements, int root, int bottom) { int maxC, rightC, leftC; // maxChild, rightChild, leftChild leftC = root * 2 + 1; rightC = root * 2 + 2; if (leftC <= bottom) { if (leftC == bottom) maxC = leftC; else { if (elements[leftC] <= elements[rightC]) maxC = rightC; else maxC = leftC; } if (elements[root] < elements[maxC]) { Swap(elements, root, maxC); reHeapDown(elements, maxC, bottom); } } }

/** @pre int array @post array two items swapped @param arr address of array @param x int subscript to be swapped @param y int subscript to be swapped swap the contents of two elements of an array */ void Swap(int * elements, int x, int y) { int temp = elements[x]; elements[x] = elements[y]; elements[y] = temp; }

void heapSort(int * elements, int start, int end) { reHeapDown(elements, start, end); for (int i = 0; (end - i) > start; ++i) { Swap(elements, start, end - i); reHeapDown(elements, start, end - i - 1); } }