Does the latest version of make_heap run in O(n)

[Morwenn]

I am pretty bad a complexity analysis, but reading again how a make_heap function runs in O(n) time and not in O(n log n) time makes me thing that the poplar::make_heap implementation based on binary carry sequence actually runs in O(n):

• When an element corresponds to the root of a single-element poplar, sift is never called. Those elements constitute half of the heap.
• When an element corresponds to the root of a three-element poplar, sift is called but can't go deeper than one level. Those elements constitute a quarter of the heap.
• For roots of bigger poplars, the number of such elements in always halved while the maximum depth of sift increases.

I'm not able to perform a proper complxity analysis, but it looks awfully close to what makes std::make_heap run in O(n), so I'm wondering whether the same analysis applies to poplar::make_heap and whether it actually runs in O(n).

The version based on push_heap can't run in O(n) because we always need to compute the size of the last poplar in O(log n) time, but the version based on the binary carry sequence computes the size of the poplar in which an element needs to be sifted in O(1), so it might actually run in O(n) if the complexity analysis of a regular make_heap method applies.

[firejox]

The poplar heap is quite similar to the post-order heap. Hence, I think it could possibly run in O(n) time.

[Morwenn]

It does seem to describe the same data structure albeit with a different name (I'm surprised I never found this paper before) even though the tricks used to compute the element positions seem to differ. I'll read it more in detail when I have time, thanks for the link :)