In addition to its use in implementing the priority queue ADT, the binary heap data structure can also be used to sort in O(n log(n)) time. The basic idea is this. Given an array of integers (for example) we can view these integers as priorities and insert these one-by-one into a max-heap. Then we repeatedly delete items from the heap. In doing so, we are guaranteed to get the largest item in the heap and will know where to place it the output array.

Problem: In a program called heapSort.java, implement the sorting algorithm described above. Perform an experimental comparison with all other sorting techniques you have studied, i.e., selection sort, insertion sort, bubble sort, merge sort, and quick sort.