6.5-5

[wojtask]

[wojtask]

Migratable from CLRS2e's 6.5-4. Note, that the code of Max-Heap-Insert is updated.

[wojtask]

While I was arguing before that temporarily updating the key of the new object to $-\infty$ is necessary, now I am not so sure about it. We can simply leave $x.key$ unchanged in $MaxHeapInsert$ and call $MaxHeapIncreaseKey(A, x, x.key)$ at the end. This call is safe, because it won't generate the error, and will correctly get rid of the max-heap property violation that adding $x$ may have caused.

It could have been done in the CLRS2e's version of the procedure as well, by assigning $A[heapsize[A]]\leftarrow key$ before increasing the key of the new element.

Anyone would like to share their opinion on it?

[wojtask]

I got a confirmation that the Authors agreed that line 5 in Max-Heap-Insert is redundant, and that Exercise 6.5-5 is not valid (thanks to @evarga who spoke to Tom Cormen). The Authors aren't going to fix that though, so I'm leaving this exercise unsolved, with a clarification note instead.