My question is why use floor(length(a)/2)? How is it different than using length(a)? Is this the same thing?
Since every node at index $⌊𝑛/2⌋+1,⌊𝑛/2⌋+2,⋯,𝑛$ is a leaf node, it is also a root of a subtree max-heap. So no difference.
However, I want to point to another question, perhaps more interesting:
Why do we go backwards and don't start from 1 up to floor(length(a)/2)?
The answer lies in the assumptions made by
When it is called, MAX-HEAPIFY assumes that the binary trees rooted at LEFT(i)
and RIGHT(i) are max-heaps, but that A[i] might be smaller than its children,
thus violating the max-heap property.
A = [5, 3, 4, 9, 6, 1, 2], if you start from the first element (
5), it's left subtree (
3->9, 3->6) is not itself a max-heap.
Since the assumption is violated, you're not guaranteed to get correct max-heap data structure if you don't start backwards from the middle.