A. Intro
Today, we'll take a look at the priority queue and how it can be implemented using a heap. We'll close with a little practice debugging on a specific implementation of minimax.
B. Implementations of queues and priority queues
Queue
and PriorityQueue
in java.util
The java.util
library contains a Queue
interface and a PriorityQueue
class that implements Queue
. Queue
methods include the following:
offer(element)
, which adds the element to the queue (this is enqueue)peek()
, which returns but does not remove the head of the queuepoll()
, which retrieves and removes the head of the queue (returning null if the queue is empty) (this is dequeue)
Java's priority queue is implemented with a data structure called a binary min heap. In the rest of this lab, you will study and implement this data structure yourself.
As you saw in lecture, priority queues are often implemented with a heap because they allow us to quickly insert and remove objects with different priority values.
There are two flavors of binary heaps: min heaps and max heaps. They're very similar except the former organizes items by smallest and the latter organizes items by largest. Today we will be implementing a min heap.
Exercise: Implementing your own min heap
The class ArrayHeap
implements a binary min heap using an ArrayList
, just like we discussed at the beginning of this lab. Open it up and read the provided methods.
Notice in the constructor we call contents.add(null)
. Think about how this affects indexing and why we choose to add a null
element.
Fill in the missing methods in ArrayHeap.java
. As John DeNero wisely says, code that doesn't respect abstraction barriers should BURN. Respect abstraction barriers! (You should able to finish the lab without directly using the contents
ArrayList)
- First implement
getLeftOf(int i)
,getRightOf(int i)
,getParentOf(int i)
- Next, using the previously implemented methods, implement
setLeft(int index, Node n)
andsetRight(int index, Node n)
- Next, implement
min(int index1, int index2)
,peek()
,bubbleUp(int index)
,bubbleDown(int index)
- Lastly, implement
insert(T item, double priority)
,removeMin()
,changePriority(T item, double priority)
. Make sure you use thebubbleUp
andbubbleDown
methods when implementing these functions.
We have provided a very basic test located in ArrayHeapTest.java
. This test is by no means comprehensive, so we highly recommend adding your own tests.
C. Debugging
A Review of Debugging Tools
If you're still not familiar with debuggers, please take the time to review their documentation.
Exercise: Debugging an Implementation of Minimax
Now we'll take a closer look at a variation of the Minimax algorithm we saw in lecture. Consider the game Top-Bottom-Draw, wherein two players take turns drawing cards from the top or bottom of a deck. Player A's goal is to maximize her total score and Player B's goal is to minimize Player A's score.
Assume both players are playing optimally and know the order of all the cards in the deck. If Player A goes first, what is the maximum score she can achieve?
Player A only has two options: take the bottom card or take the top card. Her best choice is to take the maximum(value of top card + best score on deck after Player B takes a turn on deck with top card removed, value of bottom card + best score on deck after Player B takes a turn on deck with bottom card removed). Player B is playing to minimize Player A's score, so we can assume that he takes the minimum(Player A's best score on deck with top card removed, Player A's best score on deck with bottom card removed). Do you see why? If not, discuss the problem with a neighbor and try writing out a few examples.
This is what we want to achieve, but the code in TopBottomDraw.java is not working! Use your debugger of choice to find the error.
D. Submission
Please submit TopBottomDraw.java and ArrayHeap.java.