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.
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