This is an archive of the discontinued LLVM Phabricator instance.

Checked that complexity of std::sort_heap is 2N log(N) comparisons
ClosedPublic

Authored by nilayvaish on Feb 21 2023, 11:45 PM.

Details

Summary

https://wg21.link/LWG2444 updated the comparison complexity of

std:sort_heap to be at most 2N log (N) where N == last - first.  In the
current implementation, we invoke __pop_heap exactly N-1 times.  In each
call to __pop_heap, we first go down the heap from first to possibly
last in the function __floyd_sift_down.  Then, we possibly go back up in
the function __sift_up.

In the function __floyd_sift_down, there is loop in which one comparison
is made in each iteration.  The loop runs till __child becomes greater
than (__len - 2) / 2.  __child starts at 0 and it is at least set to 2 *
__child + 1 on each iteration.  Thus, after k iterations, __child will
be at least 2^k - 1.  After log(N) iterations,  __child >= 2^(log(N)) -
1 = N - 1 > (__len - 2) / 2.  This means that the while loop in the
function __floyd_sift_down would perform at most log(N) comparisons on
each invocation.

In the function __sift_up, there is one comparison made that will almost
always occur.  After that there is a do-while loop.  The comparison
function is invoked once in each iteration.  In the worst case, the loop
will run till __len goes down to zero.  It can start from (N-3)/2.  In
each iteration, __len goes down to (__len-1) / 2.  After k iterations,
__len will be at most (N - 2^(k+1) -1) / 2^(k+1).  Thus, __len will
become  when (N-2^(k+1)-1) < 2^(k+1)  i.e. N  < 2^(k+2) + 1.  This means
at most log(N) - 1 iterations for the loop.  So in total at most log(N)
  comparison will be performed in __sift_up.

So overall for each iteration of the loop in __pop_heap, there will at
most 2 log(N) comparisons.  So, the total number of comparisons is
at most 2 N log(N).

Diff Detail

Event Timeline

nilayvaish created this revision.Feb 21 2023, 11:45 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 21 2023, 11:45 PM
Herald added a subscriber: mgrang. · View Herald Transcript
nilayvaish published this revision for review.Feb 21 2023, 11:46 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 21 2023, 11:46 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript

Please add a test that counts the number of comparisons to show that it actually only takes 2N log(N) comparisons.

Updated the test used for testing the complexity of heap sort implementation.

Removed #include <iostream> as it is not required.

Please add a test that counts the number of comparisons to show that it actually only takes 2N log(N) comparisons.

I updated the existing test to test for more lengths at a tighter complexity than what the C++ standard requires.

Pinging reviewers!

philnik added inline comments.Mar 1 2023, 8:11 AM
libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
50

Could you move this test to libcxx/test/std and also add it to ranges_sort_heap.pass.cpp?

74

Addressed review comments.

nilayvaish updated this revision to Diff 502468.Mar 5 2023, 1:06 PM
nilayvaish marked an inline comment as done.

Addressed review comments.

nilayvaish marked an inline comment as done.Mar 5 2023, 1:07 PM
philnik accepted this revision.Mar 5 2023, 1:40 PM

LGTM with comments addressed.

libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
65–68

This comments seems to be wrong now. Same in the ranges test.

77

Also for the ranges code.

This revision is now accepted and ready to land.Mar 5 2023, 1:40 PM
nilayvaish updated this revision to Diff 502613.Mar 6 2023, 6:16 AM

Addressed review comments.

libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
65–68

Dropped lines 64-66 here and in the ranges test.

77

Added assert here and in the ranges test.