Heapsort

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.

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/
    ---     ---     ---

Illustration of Heapsort

Illustration of
Heapsort