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.