CS 3343/3341
 Analysis of Algorithms 
  Illustration of  
Heapsort

Heapsort In each case below, the heap is in black, while those nodes that are no longer part of the heap are in red. At each stage, the two elements in blue are interchanged, and the heap property restored for element 1 down through the element before the second blue element.

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 1st step of heapsort:

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

After 2nd step of heapsort:

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

After 3rd step of heapsort:

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

After 4th step of heapsort:

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

After 5th step of heapsort:

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

After 6th step of heapsort:

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

After 7th step of heapsort:

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

After 8th step of heapsort:

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

After 9th step of heapsort (All done, sorted):

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

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