Is 6.5.8 wrong?

[vivek-rd]

If 'i' is a leaf node and when A[i] > A[A.heap_size], the max_heapify function does not work in that case as the leaf node does not have any left or right sub-trees.

[Antitimofey]

This implementation should works:

HEAP-DELETE(A, i)
HEAP-INCREASE-KEY(A, i, +infinity)
HEAP-EXTRACT-MAX(A)
A.heap-size = A.heap-size - 1

Both HEAP-INCREASE-KEY and HEAP-EXTRACT-MAX cost O(lg(n)) time, so HEAP-DELETE also runs in O(lg(n)) time