CSC300: Quiz Answers [3/3]

All heaps are max oriented

Insert three elements into this heap:

                     12
           11                  03
      08        10        00        02
    04  05    07  **    **  **    **  **

Insert: 1

                     12
           11                  03
      08        10        00        02
    04  05    07  01    **  **    **  **

Insert: 9

                     12
           11                  03
      08        10        00        02
    04  05    07  01    09  **    **  **

                     12
           11                  03
      08        10        09        02
    04  05    07  01    00  **    **  **

                     12
           11                  09
      08        10        03        02
    04  05    07  01    00  **    **  **

Insert: 6

                     12
           11                  09
      08        10        03        02
    04  05    07  01    00  06    **  **

                     12
           11                  09
      08        10        06        02
    04  05    07  01    00  03    **  **

Remove three elements from this heap:

                     09
           08                  07
      05        06        00        02
    01  04    03  **    **  **    **  **

remove 9

                     03
           08                  07
      05        06        00        02
    01  04    **  **    **  **    **  **

                     08
           03                  07
      05        06        00        02
    01  04    **  **    **  **    **  **

                     08
           06                  07
      05        03        00        02
    01  04    **  **    **  **    **  **

remove 8

                     04
           06                  07
      05        03        00        02
    01  **    **  **    **  **    **  **

                     07
           06                  04
      05        03        00        02
    01  **    **  **    **  **    **  **

remove 7

                     01
           06                  04
      05        03        00        02
    **  **    **  **    **  **    **  **

                     06
           01                  04
      05        03        00        02
    **  **    **  **    **  **    **  **

                     06
           05                  04
      01        03        00        02
    **  **    **  **    **  **    **  **

Heapify this array using the first pass of heapsort:

                     07
           04                  02
      03        05        08        01
    06  09    00  **    **  **    **  **

                     07
           04                  02
      09        05        08        01
    06  03    00  **    **  **    **  **

                     07
           04                  08
      09        05        02        01
    06  03    00  **    **  **    **  **

                     07
           09                  08
      04        05        02        01
    06  03    00  **    **  **    **  **

                     07
           09                  08
      06        05        02        01
    04  03    00  **    **  **    **  **

                     09
           07                  08
      06        05        02        01
    04  03    00  **    **  **    **  **