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: [email protected]
ReportedBy: [email protected]
CC: [email protected]
__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.
_______________________________________________
LLVMbugs mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/llvmbugs
