Illustration of 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.

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

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

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

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

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

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

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

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

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

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

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