Re^3: getting the highest value in a simpler way

Am I correct in saying that insertion is O(log n) for each insertion? Therefore, if you have 500 insertions, it would be something like (sum)O(log n) (for n=1->500)??

That is no longer O(log n), but something higher than that, I believe. I don't know what would dominate, though, the O(log n), or the (1->500) sum, but I suspect the latter.

Comment on Re^3: getting the highest value in a simpler way

Replies are listed 'Best First'.
Re^4: getting the highest value in a simpler way by davido (Cardinal) on Nov 10, 2004 at 19:28 UTC
Insertion of each element individually is O(log n), for a plain heap. A Fibonacci heap does inserts in O(1), and get/delete-min's in O(log n) amortized time, but at the cost of being pretty tricky to implement correctly, though there are modules to help with that. But to your point, yes, each insert is O(log n). Dave	[reply]
Re^5: getting the highest value in a simpler way by exussum0 (Vicar) on Nov 10, 2004 at 20:35 UTC
We chatted.. if each insert costs log n, and you are doing it n times.. you get n log n, no? If you heapify an existing array, you get n... which isn't much better anyway. At least TCRC likes to claim that max and min ops are done in n time, which seems right, no? ---- Then B.I. said, "Hov' remind yourself nobody built like you, you designed yourself"	[reply]