Book Version 1.5.9 Question 11.4 Why to add every star in the heap?

#1

Hi,

I want some comments on whether my method here is correct or not for this question. Shouldn’t we just calculate distance in the beginning for each star before inserting. We will fill the maxHeap to its initial capacity k in the beginning . Once its filled we only need to do the inserts and removal for stars with distance < maxHeap.peek(). This will reduce the number of operations on heap in case if first k stars in the file are closest to earth and k<<n.

0 Likes
#2

Hey Akash,

Thanks for your question. Can you analyze the run time of your algorithm, which I think it still is O(nlogk) like the one we had now? More importantly, comparing with maxHeap.peek() is not enough since the new element may need to compare with others if the new element is pretty close star. In that situation, there is probably no difference between these two algorithms.

Please let me know what you think.

0 Likes
#3

Hi Tsung,

Thanks for responding. I agree that the time complexity will still be O(nlogk). Just wanted to explore the pros and cons of each approach. I think what you are saying is correct. In case of pretty close star it will have to trickle down in the heap. In the case where its value is greater than maxHeap.peek(), inserting and removing will be O(1) time complexity operations right ? If that’s the case then the two algos will run in almost the same time.

Thanks,
Akash

0 Likes
#4

For the case that is greater than maxHeap.peek(), it is O(1) operation for sure. Actually, I like this optimization since for the normal input, this case will be trigger pretty often when the input are reaching the end (since all the closest stars are in maxHeap already). However, from the code readability perspective, I won’t adopt that.

0 Likes