CS 3343/3341
 Analysis of Algorithms 
  Insert into Heap  

Original array:

                               ___
                             1/   \
                              \  4/
                 +-------------------------------+
                 |                               |
                ___                             ___
              2/   \                          3/   \
               \  1/                           \  3/
         +---------------+               +---------------+
         |               |               |               |
        ___             ___             ___             ___
      4/   \          5/   \          6/   \          7/   \
       \  2/           \ 16/           \  9/           \ 10/
     +-------+       +-------+          ---             ---
     |       |       |
    ___     ___     ___
  8/   \  9/   \ 10/   \
   \ 14/   \  8/   \  7/
    ---     ---     ---

After building a heap:

                               ___
                             1/   \
                              \ 16/
                 +-------------------------------+
                 |                               |
                ___                             ___
              2/   \                          3/   \
               \ 14/                           \ 10/
         +---------------+               +---------------+
         |               |               |               |
        ___             ___             ___             ___
      4/   \          5/   \          6/   \          7/   \
       \  8/           \  7/           \  9/           \  3/
     +-------+       +-------+          ---             ---
     |       |       |
    ___     ___     ___
  8/   \  9/   \ 10/   \
   \  2/   \  4/   \  1/
    ---     ---     ---

After inserting 19 at position 11 and heapifying:

                               ___
                             1/   \
                              \ 19/
                 +-------------------------------+
                 |                               |
                ___                             ___
              2/   \                          3/   \
               \ 16/                           \ 10/
         +---------------+               +---------------+
         |               |               |               |
        ___             ___             ___             ___
      4/   \          5/   \          6/   \          7/   \
       \  8/           \ 14/           \  9/           \  3/
     +-------+       +-------+          ---             ---
     |       |       |       |
    ___     ___     ___     ___
  8/   \  9/   \ 10/   \ 11/   \
   \  2/   \  4/   \  1/   \  7/
    ---     ---     ---     ---

After inserting 6 at position 12 and heapifying:

                               ___
                             1/   \
                              \ 19/
                 +-------------------------------+
                 |                               |
                ___                             ___
              2/   \                          3/   \
               \ 16/                           \ 10/
         +---------------+               +---------------+
         |               |               |               |
        ___             ___             ___             ___
      4/   \          5/   \          6/   \          7/   \
       \  8/           \ 14/           \  9/           \  3/
     +-------+       +-------+       +-------+          ---
     |       |       |       |       |
    ___     ___     ___     ___     ___
  8/   \  9/   \ 10/   \ 11/   \ 12/   \
   \  2/   \  4/   \  1/   \  7/   \  6/
    ---     ---     ---     ---     ---

After inserting 13 at position 13 and heapifying:

                               ___
                             1/   \
                              \ 19/
                 +-------------------------------+
                 |                               |
                ___                             ___
              2/   \                          3/   \
               \ 16/                           \ 13/
         +---------------+               +---------------+
         |               |               |               |
        ___             ___             ___             ___
      4/   \          5/   \          6/   \          7/   \
       \  8/           \ 14/           \ 10/           \  3/
     +-------+       +-------+       +-------+          ---
     |       |       |       |       |       |
    ___     ___     ___     ___     ___     ___
  8/   \  9/   \ 10/   \ 11/   \ 12/   \ 13/   \
   \  2/   \  4/   \  1/   \  7/   \  6/   \  9/
    ---     ---     ---     ---     ---     ---

Revision date: 2012-01-01. (Please use ISO 8601, the International Standard.)