max heap and insertion

johnnily picture johnnily · Nov 25, 2012 · Viewed 11.7k times · Source

I have the an integer array of size 10. I need to draw the complete binary tree which I did. Now I need to insert the three other elements using siftup procedure. Show the max heap following each insert.

I m not sure what is that show the max heap following each insert. is that mean i need to show the size of max heap each time i insert one element?

Definition (max heap) HEAP(X) Let X be a totally ordered set. A heap on X is either empty, ∅, or it is a complete binary tree, t, comprising nt ≥ 1 nodes to each node of which a value of X is assigned such that: value of node i ≤ value of parent of node i, i = 2,3,...,nt. The size of a heap is the number of nodes in the tree. A heap is empty if and only if its size is 0.

the definition of max heap is like this, but it looks like a bit ambiguous to me.

Answer

Juan Lopes picture Juan Lopes · Nov 25, 2012

You need to show the resulting tree after each insetion. I mean, if initially you have a heap

   3
  / \
 1   2

And you insert a 5, it will start at the last heap position and will bubble up to the heap head:

    3           5
   / \         / \
  1   2  =>   3   2
 /           /
5           1 

Analogously If you insert a 4, then:

    5           5
   / \         / \
  3   2  =>   4   2
 / \         / \
1   4       1   3