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 queue
• poll(), 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 into the heap quickly.

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. Choose either one depending on your definition of priority score.

Exercise: Implementing your own 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.

What is the purpose of contents.add(null) in the constructor?

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! That is, when you implement insert, removeMin, and changePriority, you should be using bubbleUp and/or bubbleDown, and when you implement bubbleUp and bubbleDown, you should be using getLeft, getRight, and/or getParent.
• You should be able to work on the methods in order. The first couple are relatively easier. Don't forget to write a suite of JUnit tests to test your code.

C. Debugging

A Review of Debugging Tools

If you're still not familiar with debuggers, please take the time to review their documentation. You have a variety of options to choose from, but the two most popular debuggers are listed below.

• IntelliJ
• gjdb from command line

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.