Type MAX-HEAP-INSERT (1-indexed): the −∞ trick
Type MAX-HEAP-INSERT (1-indexed): the −∞ trick
Answer
MAX-HEAP-INSERT(A, key) A.heap-size = A.heap-size + 1 A[A.heap-size] = -INFINITY MAX-HEAP-INCREASE-KEY(A, A.heap-size, key)
Append a sentinel −∞ at the new leaf, then INCREASE-KEY bubbles it up to its correct position. Reusing INCREASE-KEY keeps the code small and the precondition satisfied.