Heap

[darwinrlo]

Computing the indices of a node's children

We are given a heap, implemented as an array. We are given a node in the heap by its index in the array -- the index is i. We are given that the node has two children. Determine the array indices for the two children.

As established elsewhere, level j starts at index Power(2, j) - 1 in the array.

To introduce some pertinent variables, the level that node i is on is level j and k nodes appear before node i on level j. In terms of these variables, i = Power(2, j) - 1 + k.

The children of node i are on the next level, that is, level j+1. For each of the k nodes that appear before node i on level j, there are two (child) nodes that appear before the children of node i on level j+1. Level j+1 starts at index Power(2, j+1) - 1, so the first child of node i is at index Power(2, j+1) - 1 + 2k. Refactoring:

Power(2, j+1) - 1 + 2k = 2*Power(2, j) - 1 + (k + k) = [Power(2, j) + Power(2, j)] - 1 + (k + k) = [Power(2, j) - 1 + k] + (Power(2, j) + k) = i + (i - 1) = 2i - 1

So the first child of node i is at index 2i - 1. The second child is at the very next index, which is 2i.

[darwinrlo]

The first index of a level

• The first index of level 0 is 0, which is Power(2, 0) - 1.
• The first index of level 1 is 1, which is Power(2, 1) - 1.
• The first index of level 2 is 3, which is Power(2, 2) - 1.
• And so on.

In general, the first index of level k is Power(2, k) - 1.

[darwinrlo]

Heap Property

If a node has children, then its value is smaller than its children's values. If a node has two children, there is no necessary ordering on the children.

[darwinrlo]

On p. 116 of Algorithms Illuminated Part 2, it says, "We have a full binary tree, but does the heap property hold?"

A full binary tree is one in which each node either has 0 or 2 children. He means "complete binary tree," which is a binary tree in which every level is filled except for perhaps the last, which if unfilled would be filled from left to right.

[darwinrlo]

Claim: Every parent-child pair created from a sift-up existed in the tree prior to insertion.

Since each node only has one parent, there is only one path upward from a leaf to the root. The first upward sift breaks up a parent-child pair. That pair is reunited if another upward sift is done. Every upward sift after the first and except for the last both breaks up a parent-child pair and re-unites a parent child-pair along the one leaf-to-root path.

[darwinrlo]

Claim: At most one parent-child pair violates the heap property after adding an element to the end of the array or sifting up.

Initially, the new node is added at the end. If there is a violation, it is between this new node and its parent. All the other parent-child relationships existed before the insertion.

After a sift-up, there are two new parent-child relationships. The new node is now a parent of its former parent's child. And it is now the child of its former parent's parent. Due to the heap property, it is smaller than its new child that's not its former parent. This leaves just the new parent-child relationship the node being inserted forms with its former parent's parent.

[darwinrlo]

Power(2, Floor(Log[2](n))) <= n <= Power(2, Ceiling(Log[2](n)))

[darwinrlo]

Computing the index of the parent

The node is either the left or right child of the parent. That is, j is either 2i - 1 or 2i.

If it's the right child, then dividing by 2 should get the exact parent index. But it's the left child, then dividing by two will yield a value that is 1/2 less than the parent index. So taking the ceiling is appropriate.

[darwinrlo]

Extracting the minimum element

Replace the root node, which is the minimum element, with the last element. Decrease the heap size by 1. As long as the heap property is violated by the formerly last element, swap it with its smaller child. At some point, the heap property will be restored, possibly by "bubbling" the formerly last element all the way to the last level.