Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time, into an initially empty binary heap. b. Show the result of using the linear-time algorithm to build a binary heap using the same input. Show the result of performing three deleteMin operations in the heap of the previous exercise.

Explanation:

A)

10 10 10 1 1

/ / \ --> / \ / \

12 12 1 12 10 12 10

/

14

1 1 1 1

/ \ / \ / \ / \

12 10 --> 6 10 6 10 --> 6 5

/ \ / \ / \ / / \ /

14 6 14 12 14 12 5 14 12 10

1 1 1 1

/ \ / \ / \ / \

6 5 6 5 6 5 --> 3 5

/ \ / \ / \ / \ / \ / \ / \ / \

14 12 10 8 14 12 10 8 14 12 10 8 6 12 10 8

/ / \ / \

15 15 3 15 14

After inserting all 1

/ \

3 2

/ \ / \

6 7 5 4

/ \ / \ / \ / \

15 14 12 9 10 11 13 8

b)

First level build : 10

/ \

12 1

/ \ / \

14 6 5 8

/ \ / \ / \ / \

15 3 9 7 4 11 13 2

Heap bottom level: 10

/ \

12 1

/ \ / \

3 6 4 2

/ \ / \ / \ / \

15 14 9 7 5 11 13 8

Heap next level up: 10

/ \

3 1

/ \ / \

12 6 4 2

/ \ / \ / \ / \

15 14 9 7 5 11 13 8

Final heap: 1

/ \

3 2

/ \ / \

12 6 4 8

/ \ / \ / \ / \

15 14 9 7 5 11 13 10

c)

Duing the first time,

First, assume the last element, the 8, is at the root and bubble down.

Then, assume the last element, the 13, is at the root and bubble down.

Then, assume the last element, the 11, is at the root and bubble down.

Final heap:

4

/ \

6 5

/ \ / \

13 7 10 8

/ \ / \ /

15 14 12 9 11

In the next iteration,

First, assume the last element, the 10, is at the root and bubble down.

Then, assume the last element, the 13, is at the root and bubble down.

Then, asssume the last element, the 11, is at the root and bubble down.

So, after performing all operations, the heap looks like below:

4

/ \

6 5

/ \ / \

12 7 10 8

/ \ / \ /

15 14 9 13 11

so much for the extra points :

answer///router;