Why do we bother setting the key of the inserted node to \(-\infty\) in line 2 of \(\textsc{Max-Heap-Insert}\) when the next thing we do is increase its key to the desired value?
Setting the key to \(-\infty\) might seem wasteful at first glance, but it serves an important purpose: it ensures the precondition of \(\textsc{Heap-Increase-Key}\) is satisfied.
The \(\textsc{Heap-Increase-Key}\) procedure has a built-in safety check. It verifies that the new key is at least as large as the current key, otherwise it signals an error. This prevents accidentally decreasing a key when we meant to increase it, which could violate the max-heap property in a way that \(\textsc{Heap-Increase-Key}\) cannot fix (it only bubbles elements upward, not downward).
By setting \(A[\text{heap-size}] = -\infty\), we guarantee that any actual key value will be larger than the current value. This allows \(\textsc{Heap-Increase-Key}\) to pass its validity check and proceed with inserting the element.
Think of it like this: \(\textsc{Max-Heap-Insert}\) creates a “placeholder” slot at the bottom of the heap with the smallest possible value, then delegates to \(\textsc{Heap-Increase-Key}\) to fill that slot with the actual value and bubble it to the correct position. This design follows the principle of code reuse. Rather than duplicating the upward-bubbling logic in both procedures, we use the sentinel value to make \(\textsc{Heap-Increase-Key}\) work for insertions too.