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