How to create a bunch?

Question

Suppose I have a bunch. As below:

77 / \ / \ 50 60 / \ / \ 22 30 44 55 

Now I want to insert another element 55 into this heap.

How to do it?

Option 1.

  77 / \ / \ 55 60 / \ / \ 50 30 44 55 / 22 

Option 2

  77 / \ / \ 55 60 / \ / \ 22 50 44 55 \ 30 

Option 3

  77 / \ / \ 50 60 / \ / \ 22 30 55 55 / 44 

What is the right step? And Why ? Please explain.

Answer 1

Option 1 is right. As we begin to add children from the leftmost node, and if the parent is lower than the one just added, we will replace it. And so it will continue until the child receives a parent who has a value greater than that.

Your source tree

  77 / \ / \ 50 60 / \ / \ 22 30 44 55 

Now add 55 in accordance with the rule on most leftists.

  77 / \ / \ 50 60 / \ / \ 22 30 44 55 / 55 

But you see that 22 is less than 55, therefore replaced it.

  77 / \ / \ 50 60 / \ / \ 55 30 44 55 / 22 

Now 55 is a descendant of 50, which is still below 55, so replace them too.

  77 / \ / \ 55 60 / \ / \ 50 30 44 55 / 22 

Now it cannot be sorted anymore, because 77 is more than 55 ... So, your option 1 is right.

here you can see an example of sorting the heap in detail .. This link indicates the heap - this is a specialized tree-like data structure that satisfies the heap property: if B is a child node of A, then (A) ≥ (B). This means that the element with the largest key is always in the root of the node, and therefore this heap is sometimes called max-heap. (Alternatively, if the comparison is canceled, the smallest element is always in the root directory of the node, which leads to a mini-heap.) There are no restrictions on the number of children, each of which node is on the heap, although in practice each node has at most two.

Luck

Answer 2

Option 1, by definition, the binary form of the heap is a complete binary tree. The remaining 2 are not complete binary trees. See http://en.wikipedia.org/wiki/Binary_heap

Answer 3

Correct option: 1.

Why?

Remember that one heap property must be a complete binary tree, i.e. all their levels, with the possible exception of the last one, are completely filled, and all the nodes are as far as possible ... wikipedia?

In options 2 and 3, the element is not inserted as far as possible, and therefore the property of the complete binary tree is broken.

In relation to the final position of the element, the inserted element (son) is exchanged with their direct ancestor (father), while the son is smaller than the father.

  77 / \ / \ 50 60 / \ / \ 22 30 44 55 77 / \ / \ 50 60 / \ / \ 22 30 44 55 / 55 77 / \ / \ 50 60 / \ / \ 55 30 44 55 / 22 77 / \ / \ 55 60 / \ / \ 50 30 44 55 / 22 

Hope this will be helpful.