CS 3343/3341
 Analysis of Algorithms 
  Building a Heap  

In red are nodes that were changed from the previous picture.

Original array:

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

After restoring heap property at 5 (no change):

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

After restoring heap property at 4:

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

After restoring heap property at 3:

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

After restoring heap property at 2:

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

After restoring heap property at 1:

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

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