Lab 4 Advanced: Taking a Byte out of Heaps

In class, we discussed heaps and the need to keep them balanced in order to maintain good performance on standard operations. Our Merge algorithm accordingly checked the height of each subtree and combined elements accordingly.

What if we forbade you from computing the height (too expensive), or storing the height (takes space), or even storing even a single bit (still takes space) about the relative heights of the left and right subtrees? Could you implement the addElt and remElt in a way that maintained balanced heaps without storing or computing data about the height of the subtrees?

Why would we do this? Because figuring out how to do this exercises your data structure design muscles. (And by the way, this problem is solvable.)

For this lab, try to figure out how this would work. Group up with other students trying the advanced lab around a whiteboard or table and see what you come up with. The key to this problem lies in thinking about the data structure invariants: the heap invariant from class is fairly weak. Ask whether you can find a stronger invariant that solves this problem without your needing to store any additional data.

I don’t expect you to get to writing (much) code for this week. Write up your ideas and submit them as a txt file. The value of this exercise comes from beating your head against it for a while. If after 30 minutes you want a hint, click here (or not – you can continue to think about this for fun–just submit some thoughts so we have a record that you wored on the lab).