CODEWITHSUNDEEP
binary-tree
user220755
user220755

Reputation: 4446

Inserting elements into Binary Min Heaps

If I am inserting items: 10,12,14,1,6 into a binary min heap one item after another how would the results look like, my problem is with the following

when i start i have:

10

then 

   10
  /
 12

then

   10
  /  \
 12  14

then 

   1
  / \
 10 14
 /
12

but this is not right, so what is the right way to do that?

Note: this is a homework question, i am trying to understand the concept, if you don't feel comfortable solving the question (it is not the full question anyway) please provide an example with similar issue.

Upvotes: 7

Views: 19819

Answers (2)

Fred
Fred

Reputation: 29

step1:     10
step2:     10
          /
         12
step3:     10
          /  \
         12   14
step4:     1
          /  \
         10  12
        /
       14
step5:     1
          / \
         6  10
        / \
       12  14

Upvotes: 2

Leo
Leo

Reputation: 38180

You have to add the new element as a child (or leaf exactly) to the heap (not as root), that means you put it in the first "right" free spot (or in your heap-array, just at the end).

Then you have to re-establish the heap conditions, this is called "heapify". This happens in two phases:

  1. Repeatedly exchange the new element (general: the element that violates the heap conditions) with its parent node as long as it is smaller than the parent and it is not the root.
  2. Repeatedly exchange the new element with the child with the smallest value, until the new element becomes a leave or both child nodes are bigger than the element itself.

That means

   10
  /  \
12    14

+ 1 leads to

    10
   /  \
 12    14
 /
1

And that violates the heap conditions, so you have to heapify

    10
   /  \
  1   14
 /
12

But this is still not right, so you have to heapify again

     1
   /  \
 10   14
 /
12

And there you are... everything OK now :-)

Upvotes: 18

Related Questions