[LLVMbugs] [Bug 9636] New: __push_heap_front does two comparisons per step, only one is needed

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=9636

           Summary: __push_heap_front does two comparisons per step, only
                    one is needed
           Product: libc++
           Version: unspecified
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: All Bugs
        AssignedTo: hhinnant at apple.com
        ReportedBy: rafael.espindola at gmail.com
                CC: llvmbugs at cs.uiuc.edu


__push_heap_front is normally used to put in the correct position an element
that was previously a leaf of a heap (as in the pop_heap implementation). Since
that element was a leaf, it is likely that it will move down when placed in the
root.

An optimization is to move down the empty space at the root by swapping it with
the largest children. When the empty space becomes a leaf, the last element is
moved to its place and moved up if necessary (push_heap).

The advantage is that only one comparison per step is needed to move the empty
space down.

Wikipedia attributes the improvement to R. W. Floyd
(http://en.wikipedia.org/wiki/Heapsort), but I could not find the original
paper.

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.