Homework in Java
Write in Java
Part A: Update the java file names to include your initials at the end, send .java file only.
1. Write in-place heapSort, which takes an array of data, convert it to max heap using bottom-up
algorithm. The expected run time should be O(n), where n is the total number of data.
BubbleDown method is provided. You may test it in this Sort.
2. Write complete code for a MinHeapPriorityQueue method removeThirdMin that efficiently
removes and returns the third minimum element from the data structure. It shouldnt have
more than 3 comparisons to find the third minimum element. Your solution can make use of
the methods bubbleUp, bubbleDown and swapData but must not apply the constructor or
either of the methods add/enqueue and removeMin/dequeue.
For example, if the array contains the following elements:
1, 2, 3, 4, 5, 6, 7
It should be changed by removeThirdMin to
1, 2, 6, 4, 5, 7
Extra Credit: Modify quickSort method, to use insertionSort if sub-problem is small. Check with size
4, 8, 16, which give the best runtime?
Part B
1. Show how an initially empty min heap looks like after inserting following elements in the given
order. Draw the min heap and the array.
5, 2, 7, 8, 6, 1, 7
2. Show how a bottom-up min heap construction looks like from the above given values. Draw the
min heap and the array.
3. What is the best-case and worst-case of insertionSort?
4. What is the best-case and worst-case of mergeSort?
5. What is the best-case and worst-case of quickSort?
6. What can we do to lower, if not eliminate completely, the chances of worst-case of quickSort?
Extra Credit:
If we can access the data of a min-heap, how do we find the k-th minimum value efficiently? That
means instead of O(log n), can we speed up to O(log k)?
