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

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

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

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

Replies are listed 'Best First'.
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]

In Section Seekers of Perl Wisdom