1. (10pts) Fill in the blanks to complete the pseudo code for deleteMax(p) of a
ID: 3916658 • Letter: 1
Question
1. (10pts) Fill in the blanks to complete the pseudo code for deleteMax(p) of a priority queue p. deleteMax( max priority queue p: also integer array Al1 to n]) xzA[1] ; A[1] = Al (a) ]; n: (b)- while A[i] has a child whose value is (d) A[ (e)- else swap (Ali, AL 0)) return(k) Answer choices: (1) 1, (2) n, (3) n-1 (4) n+1, (5) x, (6) i, (7) 2i, (8) 2i+1, (9) 2i-1 (10) 1 i/2], (11) k, (12) k+1, (13) k-1, (14) 2 k, (15) 2k+1, (16) 2k-1, (17) k/2 (18) greater than, (19) less than, (20) None of the above.Explanation / Answer
Background : Max priority queue is a max heap with maximum element at the top and element at every node is greater than or equal to its children.
Whenever we want to delete max element of max heap, we remove the root and then replace it with the last element of the array. And, then down heap the array to maintain the max heap property (which is nothing but, every node is greater than or equal to its children)
In the given pseudocode, array has n elements. 1 is the starting index of the array. Assume the comments are starting with //
deleteMax(max priority queue p; also integer array A[1 to n])
// first element of the array A[1] is stored in the variable x, and A[1] is replaced with last element A[n]
//no.of.elements of the array reduces by 1, hence n=n-1
x=A[1]; A[1]=A[n]; n=n-1
//we should down heap the array starting from the first element, hence i=1
i=1
//we need to downheap the array if any of the children is greater than the node which is violating the heap property, if heap propery is obeyed, we stop there.
//hence, if A[i] has any child whose value is greater than the node, which is nothing but A[i]
while A[i] has a child whose value is greater than A[i]
//now we need to find an element in both the children to swap..
//left child is A[2i], right child is A[2i+1]. If left is greater than or equal to right, k=left else k=right
if A[2i]>=A[2i+1]
k=2i
else
k=2i+1
//after finding the element to swap, swap it with A[i], the index of element to be swapped is stored in k.
swap(A[i],A[k])
//start checking the property again from the same place where we swapped which is nothing but k.
i=k
//once all the nodes satisfy the heap property, we come out of the loop and return x which is the max element of the array.
return x
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.