CS 3343/3341, Extract Maximum

CS 3343/3341
Analysis of Algorithms

Extract Maximum
from Heap

In each case,

The elements A[1] and A[heapsize] are interchanged.
The element A[heapsize] is saved for return.
The variable heapsize is decremented by 1, and
The heap property is restored.

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

16 extracted, heapsize == 9:


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

14 extracted, heapsize == 8:


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

10 extracted, heapsize == 7:


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

9 extracted, heapsize == 6:


                               ___
                             1/   \
                              \  8/
                 +-------------------------------+
                 |                               |
                ___                             ___
              2/   \                          3/   \
               \  7/                           \  3/
         +---------------+               +---------------+
         |               |               |
        ___             ___             ___
      4/   \          5/   \          6/   \
       \  4/           \  2/           \  1/
        ---             ---             ---

8 extracted, heapsize == 5:


                               ___
                             1/   \
                              \  7/
                 +-------------------------------+
                 |                               |
                ___                             ___
              2/   \                          3/   \
               \  4/                           \  3/
         +---------------+                      ---
         |               |
        ___             ___
      4/   \          5/   \
       \  1/           \  2/
        ---             ---

7 extracted, heapsize == 4:


                               ___
                             1/   \
                              \  4/
                 +-------------------------------+
                 |                               |
                ___                             ___
              2/   \                          3/   \
               \  2/                           \  3/
         +---------------+                      ---
         |
        ___
      4/   \
       \  1/
        ---

4 extracted, heapsize == 3:


                               ___
                             1/   \
                              \  3/
                 +-------------------------------+
                 |                               |
                ___                             ___
              2/   \                          3/   \
               \  2/                           \  1/
                ---                             ---

3 extracted, heapsize == 2:


                               ___
                             1/   \
                              \  2/
                 +-------------------------------+
                 |
                ___
              2/   \
               \  1/
                ---

2 extracted, heapsize == 1:

1 extracted, heapsize == 0:

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