digitalmars.D - Why does buildHeap sift both down and up?
- Andrei Alexandrescu (12/12) Jan 15 2016 I was looking through the heap primitives in std.algorithm.sorting and
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 2016