In addition to serving as an efficient means for comparison-based sorting, heapsort also pro- vides a great means for implementing priority queues. This problem deals with a maximum priority queue. (a) Write psuedocode for Increase Key (i, key), where i is the index in the heap of the element whose key is being changed, and key is the new key value for the element. You can assume that the function is only called when key > A[i]. Your psuedocode should use a loop (as opposed to recursion). SOLUTION: Increase Key (A[1,...,n].key): # Safe to assume A[i] 1 and A[i] > A[parent(i)]: swap(A[i], A [parent(i)] i - parent(i) } (b) Prove that this algorithm is correct (i.e., that it restores the heap property to the entire array.) Be careful and precise: identify loop invariants and inductively show that these invariants are maintained. In addition to serving as an efficient means for comparison-based sorting, heapsort also pro- vides a great means for implementing priority queues. This problem deals with a maximum priority queue. (a) Write psuedocode for Increase Key (i, key), where i is the index in the heap of the element whose key is being changed, and key is the new key value for the element. You can assume that the function is only called when key > A[i]. Your psuedocode should use a loop (as opposed to recursion). SOLUTION: Increase Key (A[1,...,n].key): # Safe to assume A[i] 1 and A[i] > A[parent(i)]: swap(A[i], A [parent(i)] i - parent(i) } (b) Prove that this algorithm is correct (i.e., that it restores the heap property to the entire array.) Be careful and precise: identify loop invariants and inductively show that these invariants are maintained