HW16: Heapsort

To write and use a priority-queue implementation.

This is optionally a partner assignment.

Download Heap.java and PriorityQueue.java.

1. Write an array-based Max-Heap implementation called ArrayHeapImplementation. Include a main method to test its functionality.
2. Write a heap-based Max-Priority-Queue implementation called HeapPriorityQueueImplementation. Include a main method to test its functionality.
3. Use your priority queue to implement heapsort. Time the algorithm and compare its performance to mergesort on inputs of a variety of sizes. Note that your heapsort will produce items in descending order by priority, whereas mergesort will put them in ascending order. If that's the only difference between their outputs (that they're the reverse of each other), this is fine.
4. Write your timing observations up in a plaintext file called heap-vs-merge.txt.

Zip up all your implementation files and your timing writeup into hw16.zip and submit it on Moodle.

• Heap implementation — 11 points
• Heap test method — 2 points
• Priority Queue implementation — 1 point
• Priority Queue test method — 1 point
• Heapsort implementation — 1 point
• Heapsort timing code — 2 points
• Heapsort timing writeup — 2 points
• Comments, Style, and Design — 5 points