Fix `push` to be O(1) as promised.

kanwei / algorithms

Ruby algorithms and data structures. C extensions

http://kanwei.github.io/algorithms/

MIT License

2.67k stars 352 forks source link

Closed BMorearty closed 1 year ago

BMorearty commented 2 years ago

The method comment says it is O(1) but the code was O(n). It was doing an unnecessary loop.

This reduces the time for the "Insertion then sort" benchmark from 7.659 to 0.011.

Fixes #36.

Related: https://github.com/kanwei/algorithms/pull/46 needs to be merged. It has the benchmark that I ran.

cc @alexkalderimis

Benchmark before this change (focus on top right number):

Benchmark after this change:

BMorearty commented 1 year ago

Thanks for merging, @kanwei.

Can you please also merge #46 as mentioned above? It’s the heap benchmark I used to test this PR.