Homework # 1 (Due Date: Sunday August 20 by Midnight)

Submission:
Submit your homework via E-learning

Deliverables:
Using Winrar or 7-zip, compress all your code files into a file named StudentID_FirstName.zip

Description: Binary vs Trinary Heap
In this homework, you are asked to implement two versions of Heap Sort, one using Binary heap and the other using Trinary heap representation. Note that a trinary heap is like a binary heap, except that non leaf nodes have 3 children (left, middle, and right). The code should be modular and should have well documented implementations for HeapifyMax(), BuildMaxHeap(), Heapsort() and any others functions you may need.

Input:
A file contains n + 1 numbers. The first line of the input file will be a number representing the number of integers in the input file, followed by n integers. Experiment with various inputs (randomly generated) of various sizes.

Sample Input Files:
1000.txt
100000.txt
1000000.txt

Comparison
In your code count and report the number of data comparisons the heapsort does and prepare a table (example below). Prepare a text file with such a table and submit it along with your code. Compare the performance of heapsort using binary heap vs heapsort using trinary heap (performance equals number of comparisons). Is there any advantage of trinary heaps over binary heaps?

Input Size # of Comparisons using Binary Heap # of Comparisons using Trinary Heap
100
1000
10000
100000
...