Purpose To get practice using heaps and heapify. To understand how arrays are arranged as heaps to give the functionality of a priority queue. To learn how to do anin-placecomparison sort in O(n lg n)...

Purpose

• To get practice using heaps and heapify.


• To understand how arrays are arranged as heaps to give the functionality of a priority queue.


• To learn how to do anin-placecomparison sort in O(n lg n) time.

Background

Heap sort iscomparison-based sorting algorithm.

It is similar to selection sort, as it divides the input into a sorted and an unsorted region. It improves selection sort by reducing the time complexity with a Heap data structure instead of linear search. This allows you to select out the maximum or minimum element of a list inO(log n)time instead ofO(n)time.

We have discussed in class a way of doing Heap sort using a min-heap in which we continuously dequeue the root element of the heap (the minimum of the collection) and add it to a list. In this lab we will show how to construct Heap sortin place(no additional arrays created) using a max-heap.

Heap Sort Algorithm

To get an array sorted IN PLACE inascending order, you must prepare the list by first turning it into amax heap.

The algorithm then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap.

This repeats until the range of considered values is one value in length.

The steps are:

1. Call thebuildMaxHeap()function on the list. Also referred to asheapify(), this builds a heap from a list in O(n) operations.


2. Swap the first element of the list with the final element. Decrease the considered range of the list by one.


3. Call thebubbleDown()function on the list to sift the new first element to its appropriate index in the heap.


4. Go to step (2) unless the considered range of the list is one element.

(If you wanted the list indescending order, you could follow a similar algorithm but with a min-heap.)

ThebuildMaxHeap()operation is run once, and is O(n) in performance. ThebubbleDown()function is O(logn), and is called n times. Therefore, the performance of this algorithm is O(n+nlogn) = O(nlogn).

Time Complexity:O(n lg n)

Animation

Watchthis videoto see an animation of this algorithm.Note:this video refers to a function called "heapify" that is more similar to thebubbleDown()code provided to you in theAbstractHeapSortclass, which you should definitely take advantage of.

Problem Statement

You will be given an array of elements (they might beIntegers,Doubles,Characters,Strings, or any otherComparableobjects).

Your task is to:

1. 
   

   Complete the following methods used bybubbleDown()to get the child indexes

   
   
   
   
   • 
     leftChildIdx(int parent)takes in the parent node and returns the index in the array of the parent's left child
   
   
   • 
     rightChildIdx(int parent)takes in the parent node and returns the index in the array of the parent's right child
   
   
   
   


2. 
   

   Complete thebuildMaxHeap()method which will organize the array as a max-heap.

   
   
   
   
   • This should be down by repeatedly calling on thebubbleDown()code which is provided to you.
   
   
   • You do not need to andshould notcallbubbleDown()on every single element of the array. Do you see why?
   
   
   • You don't need to bubble down the leaves of the tree. The leaves of the tree are located in the second half of the array, since half of the nodes are leaves.
   
   
   
   


3. 
   

   Complete thelevelMap()method that returns a
   LinkedHashMap
   listing each level of the heap, level by level.

   
   
   
   
   • You don't have to use a Queue data structure to accomplish this (there is an easier way).
   
   
   • ALinkedHashMapis a Java implementation of the Map ADT that keeps the Maps's keys in order of insertion. (HashMapdoesn’t maintain any order.TreeMapsort the entries in ascending order of keys.)
   
   
   • Thekeyof the LinkedHashMap should be the level of the Heap. Thevalueof the LinkedHashMap should be a LinkedList with the nodes at that level (in order from left to right).
   
   
   • For instance, whenlevelMap()is called, this heapshould return aLinkedHashMapwhich looks like:
   
   
   
   

   
   {0=[100], 1=[19, 36], 2=[17, 3, 25, 1], 3=[2, 7]}
   
   

   
   


4. 
   

   Complete thesort()method that

   
   
   
   
   • One by one extracts the maximum element from the heap and replaces it with the last element in the array.
   
   
   • CallsbubbleDown()to bubble down the new root of the reduced heap.
   
   
   • Repeats these steps until the reduced heap is empty.
   
   
   
   

At no point in your code should you be creating or declaring any new array or ArrayLists.

Example Output

Original Array: [27, 60, 90, 72, 93, 88, 64, 68, 45, 87, 62, 59, 23, 53, 84, 50, 31, 28, 92, 61, 3, 69, 91, 7, 52, 54, 18, 73, 1, 89, 36, 58, 44, 83, 13, 48, 15, 80, 5, 41]  Heapified Array: {0=[93],  1=[92, 90],  2=[83, 91, 88, 89],  3=[68, 80, 87, 69, 59, 54, 73, 84],  4=[58, 31, 48, 72, 61, 3, 60, 62, 7, 52, 23, 18, 53, 1, 64, 36],  5=[50, 44, 27, 13, 28, 15, 45, 5, 41]}  Heapsorted Array: [1, 3, 5, 7, 13, 15, 18, 23, 27, 28, 31, 36, 41, 44, 45, 48, 50, 52, 53, 54, 58, 59, 60, 61, 62, 64, 68, 69, 72, 73, 80, 83, 84, 87, 88, 89, 90, 91, 92, 93]