Project 3
CS 271: Data Structures Fall 2019
Instructor: Ashwin Lall Due: 2019-09-30
Part 1: Heap Questions
Answer the following questions in a PDF typeset in LATEX:
1. Where in a min-heap might the largest element reside, assuming that all elements are
distinct?
2. Is an array in sorted order a min-heap? Why or why not?
3. Is a min-heap always a sorted array? Why or why not?
Part 2: Heap and Heapsort Implementation
Implement a MinHeap template class, and the heap sort algorithm. The heap sort method
should return a copy of the array in ascending sorted order. The class definition follows.
template
class MinHeap
{
public:
MinHeap(int n = DEFAULT_SIZE); // default constructor
MinHeap(KeyType initA[], int n); // construct heap from array
MinHeap(const MinHeap& heap); // copy constructor
~MinHeap(); // destructor
void heapSort(KeyType sorted[]); // heapsort, return result in sorted
std::string toString() const; // return string representation
MinHeap& operator=(const MinHeap& heap); // assignment operator
private:
KeyType *A; // array containing the heap
int heapSize; // size of the heap
int capacity; // size of A
void heapify(int index); // heapify subheap rooted at index
void buildHeap(); // build heap
int leftChild(int index) { return 2 * index + 1; } // return index of left child
int rightChild(int index) { return 2 * index + 2; } // return index of right child
int parent(int index) { return (index - 1) / 2; } // return index of parent
void swap(int index1, int index2); // swap elements in A
1
void copy(const MinHeap& heap); // copy heap to this heap
void destroy(); // deallocate heap
};
Notes:
• The second constructor should dynamically allocate A, copy the contents of initA to
A, and then call buildHeap. (Therefore, heapSort need not call buildHeap.)
• The heapSort method should return the sorted array in ascending order in the pa-
rameter named sorted. It is the responsibility of the caller to allocate sorted to be
large enough to hold the result. So here is how one could sort an array of integers
using heap sort:
int *A = new int[length];
// populate A with integers here
MinHeap heap(A, length);
heap.heapSort(A);
// print A here
• Your toString function should return a string of the underlying array in the same
format as Project 0.
• Include suitable preconditions and postconditions in the comments before each
method.
• Include unit tests (using assert and the toString method) for each of your methods.
Plot the running time of heap sort for a sequence of sufficiently large input sizes and
compare this to the running times of insertion sort and merge sort (and perhaps other
algorithms that you implemented in CS 173) and add this plot to your LATEXfile. The code
below illustrates how you can time one run of a sorting algorithm.
#include
int main()
{
# set up stuff here
timeval timeBefore, timeAfter;
long diffSeconds, diffUSeconds;
gettimeofday(&timeBefore, NULL);
# call sort here
gettimeofday(&timeAfter, NULL);
2
diffSeconds = timeAfter.tv_sec - timeBefore.tv_sec;
diffUSeconds = timeAfter.tv_usec - timeBefore.tv_usec;
cout << diffSeconds + diffUSeconds/1000000.0 << " seconds" << endl;
return 0;
}
You should acquire times for at least 100 values of n to get plots that are “smooth”
enough to empirically see the running times of the algorithms.
Submitting your work
Please upload to NoteBowl the following files:
• Your PDF file made in LATEX
• heap.cpp
• test heap.cpp
• timesort.cpp
• Makefile — this should compile your unit tests into an executable called test heap
and your sort program into an executable called timesort.
Please make sure that your code compiles and runs on the Linux machines in Olin 219.
3