3. Assume we need to build a binary max-on-top heap from keys 10, 12, 1, 14, 6,

Question

3. Assume we need to build a binary max-on-top heap from keys 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2.

a) Show the result of building this heap by inserting the above keys one at a time in the order given (from left to right), into an initially empty binary heap. (2points)

b) Show the result of using the linear-time algorithm to build a heap using the same input. (2points)

c) Show the heap from problem (a) above after executing three deleteMax operations on this heap. (2points)

I'd appreciate an explanation so I can understand what's going on! That's why I'm offering so many points! Thanks!

Explanation / Answer

keys 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2.

a) insertion.....

10

10 12 // make heap

   12 10

12 10 1

12 10 1 14 // make heap

14 12 10 1

14 12 10 1 6

14 12 10 1 6 5

14 12 10 1 6 5 8

14 12 10 1 6 5 8 15 // make heap

15 14 12 10 1 6 5 8

15 14 12 10 1 6 5 8 3

15 14 12 10 1 6 5 8 3 9

15 14 12 10 1 6 5 8 3 9 7

15 14 12 10 1 6 5 8 3 9 7 4

15 14 12 10 1 6 5 8 3 9 7 4 11

15 14 12 10 1 6 5 8 3 9 7 4 11 13

15 14 12 10 1 6 5 8 3 9 7 4 11 13 2

c) from above sol it is clear that 3 delmax operation will be needed whenever // make heap occured...

b)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.