walkccc / CLRS

📚 Solutions to Introduction to Algorithms Third Edition
https://walkccc.me/CLRS
MIT License
4.74k stars 1.26k forks source link

Problem 6-2 #484

Open Arthur-Kitsuragi opened 1 year ago

Arthur-Kitsuragi commented 1 year ago

You have written the function d-ARY-CHILD(i, j) in par. a, in par.c you are using d-ARY-CHILD(k, i), which is not correct. It should be d-ARY-CHILD(i, k). Moreover, I find no sense in using two if-clauses : if d-ARY-CHILD(k, i) ≤ A.heap-size and A[d-ARY-CHILD(k, i)] > A[i] ; if A[d-ARY-CHILD(k, i)] > A[largest]. if d-ARY-CHILD(k, i) ≤ A.heap-size and A[d-ARY-CHILD(i,k)] > A[largest] will be enough.

Arthur-Kitsuragi commented 1 year ago

I do not know if it is useful, but in par.b i found more accurate expression for height : h = floor(log d (n(d-1) + 1))

walkccc commented 1 year ago

For (b), I think you're right. Since $\Theta(\log_d n)$ is also correct, I'll leave it as it is for now. For (c), Updated the if-clause in the pseudocode.

Thank you!