You are given the sequence Compute a maxheap by sequentially

You are given the sequence Compute a max-heap by sequentially inserting A[1], A [2], ..., A[9] into the originally empty max-heap. Show the resulting heap in array format (as in the above).

Solution

Let us call the initially empty heap as H. We take number one by one,

2,

H: 2

4,

H: 2 4
H: 4 2

6,

H: 4 2 6
H: 6 2 4

8,

H: 6 2 4 8
H: 6 8 4 2
H: 8 6 4 2

10,

H: 8 6 4 2 10
H: 8 10 4 2 6
H: 10 8 4 2 6

12,

H: 10 8 4 2 6 12
H: 10 8 12 2 6 4
H: 12 8 10 2 6 4

14,

H: 12 8 10 2 6 4 14
H: 12 8 14 2 6 4 10
H: 14 8 12 2 6 4 10

16,

H: 14 8 12 2 6 4 10 16
H: 14 8 12 16 6 4 10 2
H: 14 16 12 8 6 4 10 2
H: 16 14 12 8 6 4 10 2

18,

H: 16 14 12 8 6 4 10 2 18
H: 16 14 12 18 6 4 10 2 8
H: 16 18 12 14 6 4 10 2 8
H: 18 16 12 14 6 4 10 2 8

The final heap is 18 16 12 14 6 4 10 2 8.