1.
a.
Initial Heap array is : 45, 34, 25, 12, 13
Operation Insert: 20
Now array is : 45,34,25,12,13,20
I 1 2 3 4 5 6 Runtime Explanation of Algorithm A[I] 45 34 25 12 13 20 1 Apply Bottom-up approach
MaxHeapify(6)
Cycle 1 45 34 25 12 13 20 1 Parent Node=6/2=3
A[3]>A[6], So stop here.
Max Heap is: 45, 34, 25, 12, 13, 20 Total runtime= 2
45
34 25
12 13
45
34 25
12 13 20
b.
Array : 45, 34, 25, 12, 13, 20
Delete at Position 3
I 1 2 3 4 5 Runtime Explanation of Algorithm
A[I] 45 34
(I)
20 12
(L)
13
(R)
N = 6, I = N/2 = 2
MaxHeapify(2)
Cycle 1 45 34 20 12 13 2 I=2, L=4, R=5
Check largest children, between A[L] and A[R],
A[R] is largest, check if A[5] > A[2], swap them,
and MaxHeapify(5), and if A[5]
here.
45 34 20 12 13
Max Heap is: 45, 34, 20, 12, 13 Total runtime= 2
2.
Array : 16, 34, 8 , 20, 5
Insert 16 as a root
Insert 34: 34<16(Insert in right)
45
34 20
12 13
16,1
Insert 8: 8<16 (Insert in left)
Insert 8: 20>16 (Insert in Right of 16)
20<34(Insert in left of 34)
Insert 5: 5<16 (Insert in Left of 16)
5<8 (Insert in left of 8)
16,1
34,2
16,1
8,3 34,2
16,1
8,3 34,2
20,4
16,1
8,3 34,2
5,5 20,4
Search 38;
1st Cycle : 38>16 so search in right sub-tree
2nd-Cycle: 38>34 so search in right sub-tree
There is no any subtree so data not found.
Search 8:
1st- Cycle: 8<16 so search in left sub-tree
2nd-Cycle: 8==8, So data found at position 2
3.
1, 4, 7, 12, 20, 34, 56, 60, 71, 82, 90, 111, 124, 156
I start searching from the middle data. If...