5
$\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$
3
$\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.

| cite | improve this answer | |
$\endgroup$
3
$\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.

| cite | improve this answer | |
$\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$

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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.