poplar-heap
poplar-heap copied to clipboard
Morwenn
make_heap and sort_heap for a poplar heap with O(1) extra memory
I had forgotten about it in the meantime, but I [asked on /r/compsci][1] whether the final `make_heap` ran with the anticipated time complexity. While it didn't give me a clear...
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...
Inspired by bottom-up heapsort, it consists in changing the `sift` operation to perform a deep-dive to find the biggest leaf of a semipoplar while performing a single operation per level,...