Purpose:
To explore PriorityQueues, and everything related to the Heap data structure.
Part 1: The Priority Queue
In this lab we willwork with a few of the final CS super-structures: Priority Queues and Binary Heaps
Exercise 1:
Create a class to represent a priority queue. Just like our earlier representations of Stacks and Queues, your's will wrap an ArrayList with different add and remove operations that add and remove an element.
The other thing that we need to keep track of is a Comparator that tells us how the elements of our Queue should be prioritized. Make sure your Comparator is passed to your constructor... but start with an empty ArrayList.
The key of a Priority Queue is how elements are added and removed.Exercise 2:
Implement the method isEmpty that determines if this Priority Queue does not have any elements.
Exercise 3:
Implement the void method add that adds the given element to this Priority Queue.
In our case, the add method can just put the element anywhere in the underlying list, since our magic will be in the poll and remove methods.
Exercise 4:
Implement the method poll that returns the minimum element in the underlying list, according to this Priority Queue's Comparator.
Exercise 5:
Implement the method remove that removes (and returns) the minimum element in the underlying list, according to this Priority Queue's Comparator.
Exercise 6:
Test your structure by implementing a Comparator<Integer>, and inserting/removing/polling your structure using integers in a random order.
Make sure you always get the minimum when you poll and remove.
Part 2: Using PQ to Sort (HeapSort)
Now that you've got an implementation of a Priority Queue, we can implement our easiest sorting algorithm yet (which we saw in class).
Exercise 7:
Create an Algorithms class to contain our sorting methods.
In your class implement a private static method heapify that takes an ArrayList<X> and a Comparator<X>, and returns a PriorityQueue that contains all the elements from the list.
Exercise 8:
Implement a private static method destroyHeap that takes a PriorityQueue and removes all its elements, adding them to a new ArrayList, (notice that they will be in order).
Exercise 9:
Use your two methods to implement a public static method heapSort that takes an ArrayList<X> and a Comparator<X>, and returns new sorted ArrayList.
Notice that only the sort method is public? That's so that other classes can't call our helper methods with bad arguments.
Exercise 10:
Write some tests for your sort method using your Comparator from before.
Part 3: Introducing the efficient PQ (the Heap)
As we saw in class, A Heap is a data structure that is like a binary search tree, but instead of ordering elements left to right, we only gaurentee elements along a path are ordered top to bottom (root to leaf); siblings have no other relation.
More precisely, a Heap is a complete binary search tree where all levels filled except the last, and any missing elements in the last level are to the right. Any given element in the tree is of higher priority than all the elements of its two children (left and right).
Notice that the left and right trees have no constraints on eachother, just with the parent and any of their own children.
Exercise 11:
Design a class to represent a Heap. The heap is rather similar to your PriorityQueue in fact, make it extend your earlier class to save us the effort.
You'll have to create a constructor that accepts a Comparator<X> and calls the super constructor.
We represent a complete binary search tree using an ArrayList such that given an index i, the parent of i is located at index (i-1)/2, its left child is located at index (i*2)+1, and its right child is located at index (i*2)+2.
Because the tree is complete, there are never any empty indices in the middle of the list.
Exercise 12:
Implement a boolean hasLChild method that determines whether the given index has a valid left-child in the underlying ArrayList (i.e., the calculated index is within the bounds of the array elements).
Exercise 13:
Do the same for hasRChild and hasParent. Note that any index but 0 has a parent, so that implementation is a little easier.
Exercise 14:
Override the method poll that removes the element at the root (front) of the Heap.
Now we get to add and remove. The operations rely on two operations I like to call bubbleUp and bubbleDown.
When we add to the Heap we add at the end of the underlying ArrayList. Then we just need to bubble the newly added up the representative tree until our Heap condition is satisfied.
We bubble by swapping the current element with its parent if they are out of order. If not then we are done. If we swapped then we continue to bubble our element up at its new index.
Exercise 15:
Implement a method bubbleUp that starts at a given index and moves the element up the tree by swapping it with its parent if they are in the wrong order.
You can choose to use recursion or a loop. Which do you like best?
Exercise 16:
Override the method add that places the new element at the end of the list, then bubbles it up into place.
We bubble down in a similar fashion, swapping the current element with the minimum of its left or right if they are out of order (i.e., current is greater than one of its children). If not then we are done. If we swapped then we continue to bubble our element down at its new index.
Exercise 17:
Implement a method bubbleDown that starts at a given index and moves the element down the tree by swapping it with the minimum of its children, if they are in the wrong order.
Again, you can choose to use recursion or a loop. Which do you like best?
Exercise 18:
Override the method remove that removes and returns the root element in the tree (the front of the list).
But, before returning, it moves the last element to the front, then bubbles it down into place.
Exercise 19:
Test your new Heap implementation using your tests from earlier. They should have the same behaviour right?
Exercise 20:
Change your heapSort implementation to use your new Heap and run your sorting tests to make sure they still work.