4
$\begingroup$

Taken from CLRS third edition, a procedure is given for Build-Max-Heap

function a = build_MaxHeap(a)
for i = floor(length(a)/2): -1 : 1        // i = n downto 1
     a = max_heapify(a,i);
end

My question is why use floor(length(a)/2)? How is it different than using length(a)? Is this the same thing?

function a = build_MaxHeap(a)
for i = length(a): -1 : 1        // i = n downto 1
     a = max_heapify(a,i);
end
$\endgroup$
2
$\begingroup$

It isn't, neither from a complexity nor from a correctness point of view, however, by starting the counter at $n$ you are doing useless work.

Heapify is a procedure that, if invoked on a node $v$ such that the trees rooted in its children are binary heaps, turns the tree rooted in $v$ into a binary heap. Trees that contain only one node are trivially binary heaps, therefore, you may just start running the algorithm from the first non-leaf node: invoking heapify on the leaves wouldn't have done anything, anyway.

$\endgroup$
2
$\begingroup$

There are already some answers, but I wanted to provide a maybe more straightforward explanation.

Inside your max_heapify function, you compare the value of the root node (this is the i parameter) with the values of its children. The children are located at indices like 2*i+1, 2*i+2.

So what happens in max_heapify if 2*i+ is outside the bounds of the array?

It won't swap anything or continue down the tree at all, it'll likely just be a no-op. So, there's no difference effectively.

$\endgroup$
1
$\begingroup$

In a binary max-heap, each node at a index $\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots , n$ is a leaf and is thus root of a trivial max-heap.

I am assuming that max-heap representation is like below.

PARENT($i$)

1 return $\lfloor i / 2 \rfloor$

Left($i$)

1 return $2i$

Right($i$)

1 return $2i + 1$

$\endgroup$
0
$\begingroup$

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 max-heapify procedure:

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.

Example: 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.