heap

Convert from max heap to min heap


Got this heap:

         10
        /  \
       9    8
      / \  / \
     7  6  5  4
    / \ /
   3  2 1

And i'm going to show each step when i convert it to a minimum heap from maximum. I'm not sure how i do it, any help please? Thanks.


Solution

  • try to go throught tree by levels, starting with lowest node
    If your heap is represented by array, it will be simple
    1. step
    comparing 1 with 6, and switching:

          10
         /  \
        9    8
       / \  / \
      7  1  5  4
     / \ /
    3  2 6
    

    next step - comparing 2 and 7 (and switching):

          10
         /  \
        9    8
       / \  / \
      2  1  5  4
     / \ /
    3  7 6
    

    next step - comparing 3 and 2 (and NOswitching):

          10
         /  \
        9    8
       / \  / \
      2  1  5  4
     / \ /
    3  7 6
    

    next step - comparing 4 and 8 (and switching):

          10
         /  \
        9    4
       / \  / \
      2  1  5  8
     / \ /
    3  7 6
    

    etc. this should create min-heap