Could someone explain line by line the algorithms in 4c , I\'m having trouble fo
ID: 3572592 • Letter: C
Question
Could someone explain line by line the algorithms in 4c, I'm having trouble following I think I'm ok with 4d but am wondering about 4c
4 (c) 6 marks N int number of elements in array h:int heap array of size 2 N siftDown( h, N, k) sift up( h, k) h(k) h(k) while( k sN/2) h(0) 00 while( v h(k/2) h(k) h (k/2) h(k) v 4 (d) 5 marks The number of computational steps in these operations is proportional to number of iterations of the while loop of siftUp0 or siftDown0which is at most equals the height h of the tree. For a full binary tree with height h (h+11evels) and N nodes we have: h +1 h -1 N 20 2 22 23+ 2h 2-1 i.e. N 1 2 +1 this implies h +1 log2(N +1) h log2(N +1)-1 log2 N Therefore complexity O h O(log2 N)Explanation / Answer
k = Index of the node , and h and N are given.
3(1)
/
2(2) 1(3)
shiftDown(h, N, K)
1. v = h(k) -
2. while(k<=N/2)
3. j = 2(k)
4. if(j<n && h(j) < h(j+1) )
5. j++
6. if(v>h(j)) break;
7. h(k)<---h(j) , k<--j
8. h(k)<---v
1. Element at index k
2. We have to ignore Nodes at bottom most level because they Cannot be Percolated downwards i.e Nodes are each level is hiven by 2i where i is the level and N is the total number of Nodes, hence we start from k<=N/2.
3. Left child at index k is given by 2k , right child is given by 2k +1.
4. Check if j (index) is less than the total Nodes and if Right Child Value is more than the left child Vale increment j to point to Right Child (as it is greater )
5. As explained in bulllet 4.
6. If the root (Value at Index K) is greater than the value at index j (found in point 4) , then break , beacuse all nodes are less than its children, No need to shift Downwards
7. Otherwise exchange the index at k with the max i.e j and Assign k to j.
8. Whenever the loop ends or it breaks, index at k will be replaced with key value
=======================================================================================
ShiftUp(h,k)
1. v <---h(k)
2. h(0)<---Infinity
3. while(v > h(k/2))
4. h(k) <----h(k/2)
5. k = k/2
6. h(k)<----v
1. Element at index k.
2. Make h(0) as infinty , root value as Infinite
3. Loop while element at index k is greater than its parents (because we have to percolate up) i.e parent of index k
is given by k/2
4. Exchange h(k) with h(parent) , i.e we are moving upwards
5. Make k as its parent i.e k/2
6. Do unitl we have parent greater than its index at k, otherwise when the loop finishes assign h(k) to value at v.
Thanks, I hope it clarifies.