2
$\begingroup$

What are the steps to perform bottom-up heap construction on a short sequence, like 1, 6, 7, 2, 4?

At this link there are instructions on how to do for a list of size 15, but I can't [necessarily] apply the same process to a list of 5 items (my trouble is that 5 is not enough to provide a complete tree).

$\endgroup$
  • 1
    $\begingroup$ A source that states algorithms that don't work (clearly) for some inputs is probably not worth the trouble. Have you looked in a textbook, e.g. CLRS? $\endgroup$ – Raphael Apr 21 '13 at 14:15
  • $\begingroup$ What does CLRS stand for? $\endgroup$ – CodyBugstein Apr 21 '13 at 22:57
  • 1
    $\begingroup$ Oh, sorry. Introduction to Algorithms by Cormen et al. $\endgroup$ – Raphael Apr 21 '13 at 23:07
4
$\begingroup$

Five nodes is plenty to make a tree. See for example here. His first example has 6 nodes, not 5, but it should get you started.

A heap is a binary tree with all levels filled except, perhaps, the last. The last level is filled in left-to-right until you run out of elements.

So yours would start out like this:

enter image description here

The heap invariant is that each parent is smaller than both its children. In the heap construction algorithm you work bottom up, restoring the heap invariant. One way to do this is a recursive post-order tree traversal:

Heapify (x):
    if (x->is_leaf) return x
    l = Heapify (x->left_child)
    if (exists(x->right_child)):
        r = Heapify (x->right_child)
        if ((r->value < x->value) && (r->value < l->value)):
            swap(r->value, x->value)                    # r->value was smallest
    if (l->value < x->value):
        swap(l->value, x->value)                        # l->value was smallest
    return x

In actual code for heaps the heap is often represented as an array with the elements stored top-to-bottom and left-to-right in each level. The first element is the root, the second and third elements are the children of the root, and so on. In this case you can do the initial heap creation by working backwards through the array to get a post-order tree traversal for cheap (i.e., as an iterative algorithm that doesn't need to recurse).

$\endgroup$
  • 1
    $\begingroup$ Thanks, but you misunderstood my question. I know what a heap is and I know that you can make a heap out of 5 nodes - heck, you can make a heap out of one. My question was, what is the standard process for bottom up construction of a heap, starting out with five known nodes (similar to what is done at the link I provided for 15 nodes). $\endgroup$ – CodyBugstein Apr 21 '13 at 3:19
  • 1
    $\begingroup$ I did not misunderstand. I gave you the recursive pseudo-code because that is the easy way to understand how to do the bottom-up construction with a number of nodes other than $2^n-1$. Just follow the pseudo code and you'll have your answer in about 30 seconds. $\endgroup$ – Wandering Logic Apr 21 '13 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.