We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I think I am missing something. When I add a new element, I put it at the very end of the array. Then, I find its eventual position by swim()ing up the tree. Could you post your code so I can follow your logic much more clearly please?
It is a matter of taste in fact. Since the heap is not a binary search tree, there is no guarantee that the element we are looking for will be either in the right or in the left subtree. We can also scan through the whole array as you have mentioned. In any way, the worst case time complexity won't change. My search has a slim chance of having a better average case time complexity but I cannot prove theoretically. Both are ok in this problem.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
QHEAP1
You are viewing a single comment's thread. Return to all comments →
I think I am missing something. When I add a new element, I put it at the very end of the array. Then, I find its eventual position by
swim()
ing up the tree. Could you post your code so I can follow your logic much more clearly please?It is a matter of taste in fact. Since the heap is not a binary search tree, there is no guarantee that the element we are looking for will be either in the right or in the left subtree. We can also scan through the whole array as you have mentioned. In any way, the worst case time complexity won't change. My search has a slim chance of having a better average case time complexity but I cannot prove theoretically. Both are ok in this problem.