Lab 8: Binary Heap
- Pick a partner.
- 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.
- Put your partner's name with yours in the header of the file.
- If your partner is unable to complete the lab, your maximum grade is a 90%.
- Copy everything from
/users/smatzko/212/public/ to your folder.
binheap.cpp to have the following methods:
- 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.
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.
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.
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.
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.)
- Test with provided main and compare output to "out". Make sure the insertion and
delete_min operations makes sense to you.
Turn in all of the code, and the Makefile.
sendlab.212.302 8 *.cpp *.h Makefile