Can someone explain what “number of times it descends in the tree is at most h more than number of times it ascends” and how O(h+k) is coming to be?
O(h+k) bound in Problem 15.3
Hi @googlejob,
h comes from the fact finding the smallest element (which locates at the leftmost child), which might be O(h) deep. k comes from the fact you need find k smallest elements.
0 Likes