max heap and insertion

Question

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.

`the definition of max heap is like this, but it looks like a bit ambiguous to me.` Which part looks ambiguous to you? That's exactly the part on which you need to focus your question. — phant0m, Nov 25 '12 at 17:14

score 9 · Answer 1 · answered Nov 25 '12 at 19:57

9

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

answered Nov 25 '12 at 19:57

Juan Lopes

10,143
2
25
44

this answer deserves much more votes, thanks for great demonstration. – M.kazem Akhgary Jan 22 '18 at 14:16

score 4 · Accepted Answer · answered Nov 25 '12 at 17:10

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.

score 1 · Answer 3 · answered Mar 24 '18 at 02:03

1

In heap, at any moment, from root node to the leaf node is ordered and linear:

When you insert a element to the next slot in heap, the line's order will be changed:

so, the final step of insertion become reorder a linear data structure: bubble sort

answered Mar 24 '18 at 02:03

宏杰李

11,820
2
28
35

max heap and insertion

3 Answers3