Argue the correctness of heap_increase_key (img1) using the following loop invariant:

At the start of each iteration of the while loop in line 7, the array A[0:heap_size] satisfies the max-heap property, except that there may be one violation: A[i] may be larger than parent(i).

Recall that for the proof you must show three things, as listed on img2.

img1:

img2:

\( \begin{array}{lc}1 & \text { def heap_increase_key }(A, \quad i, k e y): \\ 2 & \text { if key } A[i]: \\ 3 & \text { raise Exception("The new key } \backslash \\ 4 & \quad \text { is smaller } \backslash \\ 5 & \text { than the current") } \\ 6 & \text { A }[i]=\text { key } \\ 7 & \text { while } i>0 \text { and } A[\operatorname{parent}(i)]i, it is also true before iteration i+1 (for any i ) Termination: When the loop terminates, the invariant gives a property which can be used to show the algorithm is correct \( \begin{array}{lc}1 & \text { def heap_increase_key }(A, \quad i, k e y): \\ 2 & \text { if key } A[i]: \\ 3 & \text { raise Exception("The new key } \backslash \\ 4 & \quad \text { is smaller } \backslash \\ 5 & \text { than the current") } \\ 6 & \text { A }[i]=\text { key } \\ 7 & \text { while } i>0 \text { and } A[\operatorname{parent}(i)]i, it is also true before iteration i+1 (for any i ) Termination: When the loop terminates, the invariant gives a property which can be used to show the algorithm is correct