Argue the correctness of HEAP-INCREASE-KEY using the following loop invari- ant: At the start of each iteration of the while loop of lines 4-6, the subarray A[1.. A.heap-size] satisfies the max-heap property, except that there may be one violation: A[i] may be larger than A[PARENT(i)]. You may assume that the subarray A[1.. A.heap-size] satisfies the max-heap prop- erty at the time HEAP-INCREASE-KEY is called.

Argue the correctness of HEAP-INCREASE-KEY using the following loop invari- ant: At the start of each iteration of the while loop of lines 4-6, the subarray A[1.. A.heap-size] satisfies the max-heap property, except that there may be one violation: A[i] may be larger than A[PARENT(i)]. You may assume that the subarray A[1.. A.heap-size] satisfies the max-heap prop- erty at the time HEAP-INCREASE-KEY is called.