Efficiency of Heap.Remove

Feb 21, 2008 at 4:28 PM
Edited Feb 21, 2008 at 4:30 PM
Hi there,

Great work on the library, and I like the addition of the new extension methods :).

I noticed that the documentation for the Heap.Remove method claims an asymptotic upper bound of O(log n). However, the first line of the method is a call to Array.IndexOf, which I believe is O(n), which is faster growing than O(log n). I haven't analyzed the method in detail, but removing that call should improve the efficiency of the method so that it actually is O(log n). I haven't looked at the efficiency of any other methods--this just happened to catch my eye as I was perusing the source code :).

Cheers,
Mike
Coordinator
Feb 21, 2008 at 6:45 PM
Edited Feb 21, 2008 at 6:48 PM
Good catch. I actually added all that stuff the other day off the top of my head so bare with me on that as its sort of a skim at the moment.

Thanks for the catch.

p.s. if you find any others that are inaccurate please let me know, like I said it was skim through the source but I think the addition of this is pretty decent.


mstrobel wrote:
Hi there,

Great work on the library, and I like the addition of the new extension methods :).

I noticed that the documentation for the Heap.Remove method claims an asymptotic upper bound of O(log n). However, the first line of the method is a call to Array.IndexOf, which I believe is O(n), which is faster growing than O(log n). I haven't analyzed the method in detail, but removing that call should improve the efficiency of the method so that it actually is O(log n). I haven't looked at the efficiency of any other methods--this just happened to catch my eye as I was perusing the source code :).

Cheers,
Mike