Representing a Tree With an Array
You’ve seen two approaches to implementing a sequence data structure: either using an array, or using linked nodes. Wth BSTs, we extended our idea of linked nodes to implement a tree data structure. As discussed in the heaps lecture, we can also use an array to represent a complete tree.
Here’s how we implement a complete binary tree:

The root of the tree will be in position 1 of the array (nothing is at position 0). We can define the position of every other node in the tree recursively:

The left child of a node at position
n
is at position2n
. 
The right child of a node at position
n
is at position2n + 1
. 
The parent of a node at position
n
is at positionn/2
.
Working With Binary Heaps
Binary Heaps Defined
In this lab, you will be making a priority queue using a binary minheap (where smaller values correspond to higher priorities). Recall from lecture: Binary minheaps are basically just binary trees (but not binary search trees) – they have all of the same invariants of binary trees, with two extra invariants:

Invariant 1: the tree must be complete (more on this later)

Invariant 2: every node is smaller than its descendants (there is another variation called a binary max heap where every node is greater than its descendants)
Invariant 2 guarantees that the min element will always be at the root of the tree. This helps us access that item quickly, which is what we need for a priority queue.
We need to make sure binary minheap methods maintain the above two invariants. Here’s how we do it:
Add an item

Put the item you’re adding in the leftmost open spot in the bottom level of the tree.

Swap the item you just added with its parent until it is larger than its parent, or until it is the new root. This is called bubbling up or swimming.
Remove the min item

Swap the item at the root with the item of the rightmost leaf node.

Remove the rightmost leaf node, which now contains the min item.

Bubble down the new root until it is smaller than both its children. If you reach a point where you can either bubble down through the left or right child, you must choose the smaller of the two. This process is also called sinking.
Complete Trees
There are a couple different notions of what it means for a tree to be well balanced. A binary heap must always be what is called complete (also sometimes called maximally balanced).
A complete tree has all available positions for nodes filled, except for possibly the last row, which must be filled from lefttoright.
Writing Heap Methods
The class ArrayHeap
implements a binary minheap using an array. Fill in the missing methods in ArrayHeap.java
. Specifically, you should implement the following methods, ideally in the order shown.
 leftIndex
 rightIndex
 parentIndex
 swim
 sink
 insert
 peek
 removeMin
 changePriority
Please try to read over the entire skeleton first before starting!
JUnit tests are provided inside ArrayHeap
that test these methods (with the exception of peek and changePriority). Try out the tests as soon as you write the corresponding methods.
You may find the Princeton implementation of a heap useful. Here is a more detailed explanation of each of the methods. Unlike the Princeton implementation, we store items in the heap as an array of Nodes
, instead of an array of Key
, because we want to leave open the possibility of priority changing operations.
Submission
To submit, push your ArrayHeap.java
to Github, upload to gradescope, and submit.
FAQ
The toString method is causing a stack overflow and/or the debugger seems super slow.
The debugger wants to print everything out nicely as it runs, which means it is constantly calling the toString method. If something about your code causes an infinite recursion, this will cause a stack overflow, which will also make the debugger really slow.