C++ HOMEWORK

.

Problem 1: (The below plots of computational costs (representative of execution time) of the TreeSort and HeapSort algorithms are typical. TreeSort and HeapSort are the algorithms we discussed in our lectures: TreeSort uses a binary search tree, and HeapSort uses a binary heap.

The graphs were generated from actual runs of sorting for randomly generated vectors of integers; data points are the averages of sorting performances for 25 vectors each for data sets of sizes 10 to 50.

In the diagram, the cost of Heapsort is consistently lower than the cost of TreeSort. Explain in 1-3 sentences why it will always be the case that on average HeapSort will be more efficient than TreeSort.

Your answer here:

0

50

100

150

200

250

300

350

400

10 15 20 25 30 35 40 45 50

TreeSort

HeapSort

NlogN

Problem 2:The Priority Queue ADT is a data structure that allows access to the smallest (“highest priority”) data item at cheap cost O(1), and insertion and removal of data items are always of cost O(log N) (N = size of data set). The PriorityQueue member functions are push (insert a data time), pop (remove the smallest item), and top (access the smallest item). Provide the C++ implementations of these member functions when the data items are stored in a private data member of type BinaryHeap.

template <typename C> class PriorityQueue { public:

PriorityQueue() {} PriorityQueue(const PriorityQueue& rhs) : theheap{rhs.theheap}, theSize{rhs.theSize} {}

const C & top() const; void push(const C & x); void pop()

private int theSize; BinaryHeap<C> theheap; };

template <typename C> const C & PriorityQueue<C>∷top() const { // fill in code …

}

template <typename C> void Prioirty<C>∷push(const C & x) { // fill in code …

}

template <typename> void PriorityQueue<C>∷pop() { // fill in code …

} Continue on next page …

You may assume the following definition for class BinaryHeap, and you must use only functions from the interface of class BinaryHea to implement the PriorityQueue functions.

template <typename C> class BinaryHeap { public: BinaryHeap(); BinaryHeap(const Vector<C>&);

bool isEmpty() const; int size() cont;

const C & findMin() const; void insert(const C &); void insert(C &&); void deleteMin(); void deleteMin(C &); void makeEmpty()

private: int currentSize; Vector<C> heap;

void buildHeap() void percolateDown(int); };