Maintaining the Heap Property

A heap is a dynamic data structure, so we're going to have to contend with changes.

The most important changes can be handled by two basic operations:

• Up-heapify: The entire heap is valid, except for item i, which may violate the heap property by being smaller than its parent.
• Down-heapify: The entire heap is valid, except for the root, which might be too big. (Who violates the heap property, then?)

These don't change the shape of the tree, just which records are at which nodes.