Lab 8: Binary Heap

Lab Structure

1. Pick a partner.
2. Help each other with the code as needed. Do not type for your partner and avoid dictation, but make sure your partner is able to finish the assignment.
3. Put your partner's name with yours in the header of the file.
4. If your partner is unable to complete the lab, your maximum grade is a 90%.

Assignment

1. Copy everything from /users/smatzko/212/public/ to your folder.
2. Update binheap.cpp to have the following methods:
   1. A constructor: the "tree" is stored in a vector. Be sure to make the vector with element 0 already created (since we will not be using it). You can create a vector with one element at initialization.
   2. bool has_child (uint index) const; The method is to prevent percolating down from going too far. A node has at least one child if its index is <= half of the size.
   3. uint size() const; The only difference between the size of the heap and the vector is that is that the vector is one (1) larger. The method helps prevent confusion about the actual tree size.
   4. void insert (const T& val); This method can have the "percolate up" algorithm built in, or you can make it a separate method. A new hole is made at the end of the array (possibly using the vector "resize" method). Then the hole is percolated up to the correct insertion point.
   5. T delete_min (); This method can have the "percolate down" algorithm built in, or you can make it a separate method. The minimum is removed and a hole is left. The bottom element is removed from the end of the vector. The hole is percolated down to find the right new location for the last node. (Remember, when you percolate down, choose the smaller child to be promoted.)
3. Test with provided main and compare output to "out". Make sure the insertion and delete_min operations makes sense to you.

Turn in