Question

Use trees to illustrate each heap a. 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. (show heap after each insert) b. Show the result of using the linear-time build heap operation using the same input.

Answer 1

Check the explanation

Step-by-step 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