www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Why does buildHeap sift both down and up?

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/algor
thm/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
Jan 15