+ while (__first + __child < __last) This is invalid when __first + __child > __last. Instead, use:
while (__child < __last - __first) Likewise for later iterator additions. + if ((__first + __child + 1) < __last && + __comp(*(__first + __child), *(__first + __child + 1))) + // right-child exists and is greater than left-child + ++__child; + + // check if we are in heap-order + if (__comp(*(__first + __child), *(__first + __start))) + // we are, __start is larger than it's largest child + break; This is slightly inefficient. Instead of computing left < right and then computing start < max(left, right), you can compute start < left and start < right, and save a comparison whenever start < left. + // we are not in heap-order, swap the parent with it's largest child Typo "it's". + swap(*(__first + __child), *(__first + __start)); This is inefficient: a swap is typically 3 moves, which is more than you need here. I think you should do what Howard's code did: rotate the loop so you first determine whether any elements need to move, and if they do, move the parent into a local variable, move each element over its parent instead of swapping, and drop the parent into the right spot at the end. + // recompute the child based off of the updated parent "recompute the first child of the updated parent"? Having a __push_heap_back and a __sift_down seems weird to me. I think we should either have __sift_down and __sift_up or __push_heap_back and __push_heap_front (and I prefer the __sift names because we're not necessarily pushing at the front any more). Is there a reason to give these different names? On Tue, Jul 15, 2014 at 12:18 PM, David Majnemer <[email protected]> wrote: > Ping. > > On Wed, Jul 9, 2014 at 3:14 AM, David Majnemer <[email protected]> > wrote: > > std::make_heap is currently implemented by iteratively applying a > > sift_up-type algorithm. > > Since sift-up is O(ln n), this gives std::make_heap a worst case time > > complexity of O(n ln n). Since the C++ standard mandates that > > std::make_heap make no more than O(3n) comparisons, this makes our > > std::make_heap out of spec. > > > > Fix this by introducing an implementation of __sift_down and switch > > std::make_heap to create the heap using it. This gives std::make_heap > > linear time complexity in the worst case. > > > > This fixes PR20161. > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
