Heap Insertion and Deletion =========================== Property to be Maintained ------------------------- In a heap, each node must follow the property that it must have a value greater than that of its children. The children have no formal relationship to maintain, except that they have values less than their parents. Therefore, every node in the tree will be of lesser value than all of its ancestors, and greater value than all of its descendents. Thus, the maximum value is stored at the root of the heap. In some cases, this property is reversed. In that case, the values of children of some node must be less than that of the parent node. In this case the minimum value of the heap is stored at the root. Also, the tree as whole should have no "spaces". This is to say that there is at most one node in the tree with one child, and that child must be a left child. Also, each tree level must be complete before additional levels can be added. For example, the following are acceptable trees: O O / \ / \ O O O O / \ / / \ / \ O O O O O O O / O BUT NOT: O O / \ / \ O O O O / / / \ / \ O O O O O O \ O This also makes sure that the tree is somewhat balanced, since each node must be added in a set order, which requires that every level be filled before another tree level can be added. Deletion and Insertion ---------------------- It is important to preserve the above properties when inserting a node into the heap. Thus, it is necessary to know where to add the next node. When deleting a node, is also important to know which node to use for the heap "fixup" (i.e. the node to replace the empty space with). In both of these cases, it is important to note the "last node added". Last Node Added --------------- In a heap, it is important to keep track of the last node added in order to maintain the "no spacing" rule mentioned above. This last node added will be the "fixup" node. Typically, the node removed is the root node, since we usually want the maximum or minimum value of a set of numbers stored in the heap. In the case of a root deletion, the "fixup" node is removed and placed at the root. The value of the "fixup" node is less than at least one child of the root's value, since it was stored in the subtree of one of the root's children. Thus, it must be "trickled down" in a manner explained in the class notes. The last node added is a little deceiving though in this case: 8 8 9 / \ / \ / \ 6 7 --add 9-- 6 7 --trickle-- 8 7 / / \ / \ 2 2 9 2 6 In this case, the "last node added" is actually the node that contains 6. So it is important to distinguish the "last node" from the "last value". Although we just added a 9, the position we actually added that node to, is the "last node" added, rather than the position that 9 eventually trickles to (in this case the root node). Pointer Implementation ---------------------- One way to keep track of the last node added is to keep a pointer to the parent of the last node added. Insertion: If the parent has two children, then since that parent would be "full", the next available node on that tree level must be found such that we do not introduce spaces into the heap. To find that node, we have to find the inorder successor of the inorder successor of the inorder successor of the current parent. The inorder successor of the current parent is the right child C. Since, C has no children, its inorder successor is the closest ancestor node A such that the right subtree of A has available slots at C's level. A's inorder successor will be the next parent node that we are looking for (Q), and should have no children. Once we find Q we set our parent pointer to point at it, and then add a left child with the new value to be added (D). Should any of the calls to inorder successor return a NIL value, we would then stop the remaining calls to inorder successor, and simply change the parent pointer to indicate the minimum value of the tree. This "wrap around" would reflect the filling up of a level with nodes, and thus we would go to the "first" node in the next level. A / \ P Q / \ / O C D If this parent has one child (which must be a left child) then the next node added would be a right child to that parent. The same parent would be kept as the "pointer to the parent of the last node added". Fixup: For a parent with two children, the next node to be used as a "fixup" node would be the right child. For a parent with one child, the next node to be used as a "fixup" node would be that left child. Once the "fixup" node is removed, the parent will be left with no children, and the next "parent" must be found. To find that we take the inorder predecessor of the inorder predecessor of the inorder predecessor of the parent. This is similar to the inorder successor mentioned above. We must also watch out for NIL values of the inorder predecessor function, and "wrap around" to the last node in the inorder traversal. Array Implementation -------------------- Although array implementation of heaps carry high costs due to the need to copy parts of the array at each trickle and the lack of dynamic allocation of space, they do make keeping track of the last node added easy. The array just grows linearly, without spaces, easily maintaining the spacing property. To add a new node, just add a value to the array (if space permits). Trickling becomes more expensive, but it is a design tradeoff.