For this assignment you need to implement a min-heap data structure in C++, and use it to sort a vector of distinct integers into ascending order.  While doing so, count the number of swap operations performed during insert and delete. The initial insertion (during insert) or replacement of the removed element (during deletion) do not count towards this.  The input vector is to be read from standard input, in the format

n value1  value2 ... valuen

Instead of just sorting the original input vector, you also need to (re-)sort vectors with elements already sorted in ascending or descending order. Afterwards, report swap counts for insertion and deletion for each of these three input vectors. For example:

Here the three outputs (original/ascending/descending) correspond to the input vectors:

2 7 0 15 -1

-1 0 2 7 15

15 7 2 0 -1

Note that some sorting algorithms perform particularly poorly or well for sorted inputs (e.g. bubble sort).  Running your code on some larger inputs can give you an idea whether or not (or to what degree) that’s the case for heapsort.

You can use CodeRunner to test your work, but must submit your assignment as usual. If teamwork is permitted and you work in a team, you must include the names and student IDs of all team members as comments in your submission, and each team member must submit the same assignment separately.

Working Example

For the original input [2,7,0,15,-1], the heap vector representing the tree is updated as follows: Insertion:                                           Deletion:

For the ascending input [-1,0,2,7,15], it is updated as follows:

Insertion:                                                          Deletion:

For the descending input [15,7,2,0,-1], it is updated as follows:

Insertion:                                          Deletion: