Lab 9: Array Heaps and Debugging Review

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:

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

We have provided a very basic test located in 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 is not working! Use your debugger of choice to find the error.

D. Submission

Please submit and