1-Show what the array would look like at each step when the heapIncreaseKey oper

Question

1-Show what the array would look like at each step when the heapIncreaseKey operation
(increase the key value of the 8th node from 2 to 20) is performed on the max-heap array shown
below:
heap = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}

2-Show what the array would look like at each step when the maxHeapInsert operation to

insert a new key with value 12 is performed on the max-heap array shown below:
heap = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1, 5}
Note: For problems 4 and 5 above, the heapIncreaseKey and the maxHeapInsert operations were
discussed in the Priority Queue section of the lecture. Only show what the arrays look like after
each step of rearranging the nodes. No need to write a program or draw the binary trees.
Note: The answers for problems 4 and 5 would look something like this:
Step 0: heap = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}
Step 1: heap = {[the sequence of numbers after step 1]}
Step 2: heap = {[the sequence of numbers after step 2]}
. . .
Finally: heap = {[the sequence of numbers after completion]}

Explanation / Answer

For Problem No. 1. Heap Increase Key

Original maxheap : (16,14,10,8,7,9,3,2,4,1)

After replacing 8th element 2 with 20.

Step 1 heap : {16,14,10,8,7,9,3,20,4,1}

Step 2 heap : {16,14,10,20,7,9,3,8,4,1}

Step 3 heap : {16,20,10,14,7,9,3,8,4,1}

Step 4 heap : {20.16,10,14,7,9,3,8,4,1}

For Problem No. 2. Max Heap Insert

Original maxheap : = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1, 5}

After inserting element 12

Step 1 heap : {16, 14, 10, 8, 7, 9, 3, 2, 4, 1, 5,12}

Step 2 heap : {16, 14, 10, 8, 7, 12, 3, 2, 4, 1, 5,9}

Step 3 heap : {16, 14, 12, 8, 7, 10, 3, 2, 4, 1, 5,9}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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