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:
- Call the
buildMaxHeap()
function on the list. Also referred to asheapify()
, this builds a heap from a list in O(n) operations.
- Swap the first element of the list with the final element. Decrease the considered range of the list by one.
- Call the
bubbleDown()
function on the list to sift the new first element to its appropriate index in the heap.
- 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 theAbstractHeapSort
class, 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 otherComparable
objects).
Your task is to:
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
Complete thebuildMaxHeap()
method which will organize the array as a max-heap.
- This should be down by repeatedly calling on the
bubbleDown()
code which is provided to you.
- You do not need to andshould notcall
bubbleDown()
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.
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).
- A
LinkedHashMap
is a Java implementation of the Map ADT that keeps the Maps's keys in order of insertion. (HashMap
doesn’t maintain any order.TreeMap
sort the entries in ascending order of keys.)
- The
key
of the LinkedHashMap should be the level of the Heap. Thevalue
of the LinkedHashMap should be a LinkedList with the nodes at that level (in order from left to right).
- For instance, when
levelMap()
is called, this heap
should return aLinkedHashMap
which looks like:
{0=[100], 1=[19, 36], 2=[17, 3, 25, 1], 3=[2, 7]}
Complete thesort()
method that
- One by one extracts the maximum element from the heap and replaces it with the last element in the array.
- Calls
bubbleDown()
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]