## 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.

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)`

and`setRight(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 the`bubbleUp`

and`bubbleDown`

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.