1. Heapsort:

Implement the heap sort in the form of a template function:

 template  void heap_sort(T data[], int length) 

The heapsort works in two phases: build a heap then destroy the heap.

1) To build the heap, you consider the data array to hold a heap at the beginning of the array with un-heaped data after it

For example, at some stage the elements from index 0 to index 20 could form a heap while the elements from index 21 on are unprocessed.

Start with a heap of size 1 and the rest of the elements unprocessed

If the whole array is not yet a heap, insert the first element not in the heap into the heap.

This really just means move it up towards the root, if necessary

Repeat the previous step until the whole array is heapified

2) To destroy the heap, again the data array holds a heap followed by data not in the heap.

You start with the entire array in the heap

If there is anything left in the heap, remove the largest swap the largest element in the

heap (the first one) with the last element in the heap and then move the new first element

down to its proper place

Repeat previous step until the heap is size one

Testing the function: Create a method

 template  void test_sorted(T data[], int length) 

That will check that the array data is sorted. (Just compare adjacent elements through the array). If any elements are out of place, print a message and exit the program. If all elements are properly sorted, print a suitable message and return.

Create another method

void test_heapsort(int length) 

This function will create an array of the given length and fill it with random numbers. It will sort the array using heapsort (above) and then call test_sorted.

Use

 srand(time(NULL)); 

to initialize the random number generator so you get different numbers each time the program runs. You will need to include the system file .

// Heap.h

#ifndef HEAP_H #define HEAP_H

/** * This class implements a heap as described in the text. * We will treat it as a priority queue. */

template class heap { public: static const int CAPACITY = 10;

heap() { size = 0; }

bool is_empty() const { return size == 0;} bool is_full() const { return size == CAPACITY; }

/** * Remove the largest value from this heap and return it. * * Precondition: heap is not empty. */ T remove();

/** * Inserts the 'value' into the heap. * * Precondition: heap is not full */ void insert(const T& value); void heap_sort(T data[], int length); void test_sorted(T data[], int length);

/** * Check if the heap is valid. * Prints out each parent and its children (for all nodes with children) * Stops when a parent is less than one or both of its children * Prints 'check' for each parent that is greater than or equal to its children */ bool check_heap();

private: T data[CAPACITY]; int size; };

#include "Heap.template"

#endif // HEAP_H

// Heap.template

#include #include #include #include

/* * parent index is p, children are at indices 2*p+1 and 2*p+2 * You must check that those are in range * * child index is c, parent index is (c-1)/2 (integer division) */

/** * Inserts the 'value' into the heap. * * Precondition: heap is not full */ template void heap::insert(const T& value) { assert(!is_full());

//std::cout << size << std::endl;

// add the value to a new node in proper position data[size] = value; size++;

// move the value up the tree as needed int child = size-1; // index of the new 'node' int parent = (child-1)/2; // index of the parent

while((child > 0) && (data[parent] < data[child])) { // swap parent and child values T tmp = data[parent]; data[parent] = data[child]; data[child] = tmp; // update parent and child child = parent; // this is where new value is! parent = (child-1)/2; }

// it's a heap!

}

template void heap_sort(T data[], int length) { }

template void test_sorted(T data[], int length) { }

/** * Remove the largest value from this heap and return it. * * Precondition: heap is not empty. */ template T heap::remove() { assert(!is_empty());

// grab first element, save it for return later T save = data[0];

// copy last value in list to the beginning // decrement size data[0] = data[size-1]; size--;

// size--; // data[0] = data[size];

// sift the new first element down until it finds its place int parent = 0; int left_child = 2*parent+1; int right_child = 2*parent+2; bool still_working = true;

while(still_working && left_child < size) { // while the parent has at least one child if(right_child >= size) { // only the left child to worry about if(data[parent] < data[left_child]) { // out of order, so swap them T t = data[parent]; data[parent] = data[left_child]; data[left_child] = t; parent = left_child; still_working = false; // we must be done! } else { still_working = false; } } else { // two children if(data[left_child] > data[right_child]) { //left child larger if(data[parent] < data[left_child]) { // out of order, so swap them T t = data[parent]; data[parent] = data[left_child]; data[left_child] = t; parent = left_child; } else { still_working = false; } } else { // right child larger if(data[parent] < data[right_child]) { // out of order, so swap them T t = data[parent]; data[parent] = data[right_child]; data[right_child] = t; parent = right_child; } else { still_working = false; } } left_child = 2*parent + 1; right_child = 2*parent + 2; } }

return save; }

/** * Check if the heap is valid. * Prints out each parent and its children (for all nodes with children) * Stops when a parent is less than one or both of its children * Prints 'check' for each parent that is greater than or equal to its children */ template bool heap::check_heap() { for(int p = 0; p < size; p++ ) { int cl = 2*p+1; int cr = 2*p+2; std::cout << std::setw(5) << p << std::setw(10) << data[p]; if(cl < size) { // p has a left child? std::cout << std::setw(10) << data[cl]; if(data[p] < data[cl]) { std:exit(1); } } if(cr < size) { // p has a right child? std::cout << std::setw(10) << data[cr]; if(data[p] < data[cr]) std::exit(1); } std::cout << std::endl; } return true; }