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.
Simply put, a max heap is a heap where the value of the parent is greater than the value of any of its children. When you drew your initial complete binary tree, is it in a form of a max heap already? Sift-up (at my college we called it bubble-up, but besides the point) is a bit complicated to explain on a thread like this so I agree with @DanteisnotaGeek. The wikipedia article has a good diagram of how a sift-up procedure works. To show a max heap after insertion is asking you to draw the binary tree so that it satisfies the max heap property after each insertion. So in the end, you should have your initial tree, a tree with your first insertion, a second insertion, and a third insertion, so a total of 4 trees.