
27 Sep
2016
27 Sep
'16
5:41 p.m.
On 27 September 2016 at 18:55, Oswin Krause <Oswin.Krause@ruhr-uni-bochum.de
wrote:
Your solution has linear complexity, while the heaps provided have logarithmic complexity. (insertion in the middle of a vector is a linear time operation).
Yes, of course it has linear complexity, but the factors are much smaller. My test-case (which is more demanding than my use-case) with a (max heap) size of about 50'000 beats any (more intelligent) solution heads down. I'll just conclude with a quote: “In theory, theory and practice are the same. In practice, they are not.” Have a good day, degski