I was looking through the heap primitives in std.algorithm.sorting and was surprised that buildHeap() at https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm/sorting.d#L1289 uses percolate(). In turn, percolate() has two stages, one that sifts up, the other that sifts down.

In fact all you need to do is sift down and stop as soon as the heap property is preserved. I created https://github.com/D-Programming-Language/phobos/pull/3933 which as far as I understand is correct and also faster.

Could experts please illuminate me?


Thanks,

Andrei