reset password
Author Message
cthanh
Posts: 56
Posted 16:54 Apr 16, 2016 |

regarding the max-heapify algorithm:

why do you need to validate that L <= A.heap-size(line 3) or R<= A.heap-size (line 6 from page 154 in the textbook)

i have a problem when i do max-heapify(A,4) for chp 6 hw#2 problem #5

A.heap-size = 9

but when you do max-heapify(A,4), A[4] = 10

A[4] > A.heap-size, so the process terminates, but it is obviously not a max heap because the left(value 22) and right(value 20) is bigger than the root.

 

Did I misunderstand something?

Thanks

kprasanth
Posts: 3
Posted 23:40 Apr 17, 2016 |

Hi,

L <= A.heap-size (Line #3)

Here, L is not the value in heap instead it is just the index. i.e., You should not consider L as A[4] (Which is 10) rather you should consider L as 4 which is the index of left node in heap.

The same thing is applicable for the first condition (R<=A.heapsize) in Line # 6.

The values will be checked in the second condition A[L] > A[i] and A[R] > A[largest] in Line #3 and Line #6 respectively.

Hope am clear.

Thanks,

Prasanth Kannan.

cthanh
Posts: 56
Posted 22:25 Apr 18, 2016 |

that makes more sense to me.

thanks