## Lab 9: Validating a min heap

### Goals for this lab

By the time you have completed this lab, you should:

- understand the internal structure of a min heap
- understand how an array can be used to represent a tree
- determine whether or not items in an array are in a valid min heap order

### Lab pairing

For this lab you may work with a partner. To facilitate your submissions as a
pair you **MUST** pair up using the submission system. When you visit the
project page from where you can view all your submission you should see a link
to a page where you can join a group. Of the two people in the group, one of
you must invite the other, and the other must confirm the invitation. Once you
group up, any submissions that either you, or your partner have already made
will be visible to each other in addition to all future submissions.

### Lab preparation

After logging in, create the directory for this lab:

```
mkdir -p cs24/lab9
```

Change into the lab directory and copy the files you will need for this lab:

```
cd cs24/lab9
cp ~bboe/public_html/cs24_f13/code/lab9/* .
```

### Min heap

#### Definition

A min heap is a tree like data structure that satisfies the min heap
properties: (**1**) it is a
complete
binary tree, and (**2**) each node’s value is smaller than or equal to the
value of its children. Given these properties, the root value of the tree will
always be the smallest value contained in the tree.

**Note**: A max heap is similar to a min heap, except each node’s value is
larger than or equal to the value of its children.

#### Array-based implementation

The *complete* property of the tree makes using an array the ideal data
structure for storing heaps. Thus far we have not considered using an array to
represent a tree. Let’s look at the following heap example to see how it’s
done:

```
1
/ \
5 3
/\ /
7 9 8
```

This heap can be represented by the integer array:

```
{1, 5, 3, 7, 9, 8}
```

Note that the order is simply the breadth-first traversal order assuming we visit the left-hand-side before the right-hand-side.

Let’s assume we’re looking at the element `i`

in the array. With respect to the
tree, at what position in the array are its children located? What about its
parent?

The computation is relatively simple:

Element `i`

’s left child is at position `2 * i + 1`

, and its right child is at
position `2 * i + 2`

. Working in the other direction, element `i`

’s parent can
be found at position `(i - 1) / 2`

. Recall that when dividing integers, the
result is always rounded down (also known as the floor).

For completeness here is our array with the element values and their positions:

```
element 1 5 3 7 9 8
position 0 1 2 3 4 5
```

Element 5, at position 1, has children at `2 * 1 + 1`

, position 3, and ```
2 * 1 +
2
```

, position 4, which correspond to values 7 and 9 respectively. Likewise its
parent is `(1 - 1) / 2`

, position 0, which corresponds to value 1 as expected.

### Testing for valid heaps

In this lab you will have to implement a program, `test_heap.cpp`

, that takes
command line arguments and checks if its arguments, as integers, satisfies the
min heap property.

Your program should only produce one of two outputs, either `True\n`

or
`False\n`

, which indicates whether or not the arguments, as integers, are given
in a valid minimum heap order. The following are some example executions:

```
> ./a.out 1
True
> ./a.out 1 10 2
True
> ./a.out 2 1
False
> ./a.out 1 2 3 4 5 6 7 8 9 10
True
> ./a.out 1 2 3 4 5 6 7 8 9 1
False
```

### Submitting the assignment

Only one person in a group need submit the assignment but make sure that both you and your partner can view the submission on the submission site. If you cannot, you need to complete the making a group process. Please review the submission instructions as needed. Note that you may resubmit this assignment as many times as necessary up until the deadline.