How Can Std::Make_Heap Be Implemented While Making at Most 3N Comparisons

How can std::make_heap be implemented while making at most 3N comparisons?

A binary heap over n elements can be created in O(n) time using a clever algorithm and a clever analysis. In what follows I'm just going to talk about how this works assuming that you have explicit nodes and explicit left and right child pointers, but this analysis is still perfectly valid once you compress it into an array.

The algorithm works as follows. Start off by taking about half of the nodes and treating them as singleton max-heaps - since there's only one element, the tree containing just that element must automatically be a max-heap. Now, take these trees and pair them off with one another. For each pair of trees, take one of the values that you haven't used yet and execute the following algorithm:

1. Make the new node the root of the heap, having its left and right child pointers refer to the two max-heaps.

2. While this node has a child that's larger than it, swap the child with its larger child.

My claim is that this procedure ends up producing a new max heap containing the elements of the two input max-heaps, and it does so in time O(h), where h is the height of the two heaps. The proof is an induction on the height of the heaps. As a base case, if the subheaps have size zero, then the algorithm terminates immediately with a singleton max-heap, and it does so in O(1) time. For the inductive step, assume that for some h, this procedure works on any subheaps of size h and consider what happens when you execute it on two heaps of size h + 1. When we add a new root to join together two subtrees of size h + 1, there are three possibilities:

1. The new root is larger than the roots of both subtrees. Then in this case we have a new max-heap, since the root is larger than any of the nodes in either subtree (by transitivity)

2. The new root is larger than one child and smaller than the other. Then we swap the root with the larger subchild and recursively execute this procedure again, using the old root and the child's two subtrees, each of which are of height h. By the inductive hypothesis, this means that the subtree we swapped into is now a max-heap. Thus the overall heap is a max-heap, since the new root is larger than everything in the subtree we swapped with (since it's larger than the node we added and was already larger than everything in that subtree), and it's also larger than everything in the other subtree (since it's larger than the root and the root was larger than everything in the other subtree).

3. The new root is smaller than both its children. Then using a slightly modified version of the above analysis, we can show that the resulting tree is indeed a heap.

Moreover, since at each step the heights of the child heaps decreases by one, the overall runtime for this algorithm must be O(h).

---

At this point, we have a simple algorithm for making a heap:

1. Take about half the nodes and create singleton heaps. (You can compute explicitly how many nodes will be needed here, but it's about half).
2. Pair those heaps off, then merge them together by using one of the unused nodes and the above procedure.
3. Repeat step 2 until a single heap remains.

Since at each step we know that the heaps we have so far are valid max-heaps, eventually this produces a valid overall max-heap. If we're clever with how we pick how many singleton heaps to make, this will end up creating a complete binary tree as well.

However, it seems like this should run in O(n lg n) time, since we do O(n) merges, each of which runs in O(h), and in the worst case the height of the trees we're merging is O(lg n). But this bound is not tight and we can do a lot better by being more precise with the analysis.

In particular, let's think about how deep all the trees we merge are. About half the heaps have depth zero, then half of what's left has depth one, then half of what's left has depth two, etc. If we sum this up, we get the sum

0 * n/2 + 1 * n/4 + 2 * n/8 + ... + nk/(2^k) = Σ_{k = 0}^{⌈log n⌉} (nk / 2^k) = n Σ_{k = 0}^{⌈log n⌉} (k / 2^k+1)

This upper-bounds the number of swaps made. Each swap requires at most two comparisons. Therefore, if we multiply the above sum by two, we get the following summation, which upper-bounds the number of swaps made:

n Σ_{k = 0}^∞ (k / 2^k)

The summation here is the summation 0 / 2⁰ + 1 / 2¹ + 2 / 2² + 3 / 2³ + ... . This is a famous summation that can be evaluated in multiple different ways. One way to evaluate this is given in these lecture slides, slides 45-47. It ends up coming out to exactly 2n, which means that the number of comparisons that end up getting made is certainly bounded from above by 3n.

Hope this helps!

Is libc++'s implementation of `std::make_heap` nonconformant

This is indeed a non-conforming O(n log n) implementation.

Comparing it to the "sift up" version of heapify from the Wikipedia article on heapsort shows that it's essentially the same algorithm. Testing it on increasing integer sequences (the worst case) gives running times that nicely fit the n log n curve, and the number of comparisons needed exceeds the standard-mandated 3n figure even for small n.

Though on the average the algorithm performs well within the 3n limit, the standard mandates worst-case performance, not the average one.

How is make_heap in C++ implemented to have complexity of 3N?

You represent the heap as an array. The two elements below the i'th element are at positions 2*i+1 and 2*i+2. If the array has n elements then, starting from the end, take each element, and let it "fall" to the right place in the heap. This is O(n) to run.

Why? Well for n/2 of the elements there are no children. For n/4 there is a subtree of height 1. For n/8 there is a subtree of height 2. For n/16 a subtree of height 3. And so on. So we get the series n/22 + 2*n/23 + 3*n/24 + ... = (n/2)(1 * (1/2 + 1/4 + 1/8 + . ...) + (1/2) * (1/2 + 1/4 + 1/8 + . ...) + (1/4) * (1/2 + 1/4 + 1/8 + . ...) + ...) = (n/2) * (1 * 1 + (1/2) * 1 + (1/4) * 1 + ...) = (n/2) * 2 = n. So the total number of "see if I need to fall one more, and if so which way do I fall? comparisons comes to n. But you get round-off from discretization, so you always come out to less than n sets of swaps to figure out. Each of which requires at most 3 comparisons. (Compare root to each child to see if it needs to fall, then the children to each other if the root was larger than both children.)

How to customize std::make_heap comparison function based on some data structure?

std::make_heap takes three arguments: two iterators denoting a random access range, and a comparison function. Simply provide your custom comparison function are the third argument.

#include <algorithm>
#include <vector>

// ...

std::vector<Foo> v{/* ... */};

std::make_heap(v.begin(), v.end(), [&elementList](auto lhs, auto rhs){ 
    return elementList[lhs]->lnc > elementList[rhs]->lnc;
});

std::priority_queue and make_heap API design

I find it confusing too, but from a somewhat different perspective. Suppose that you want to sort a sequence in ascending order. There are several ways of doing it:

1. Put your data in a std::vector or std::deque and run std::sort() using std::less.
2. Put your data in a std::list and run std::list::sort() using std::less.
3. Insert your data in a std::set that is configured with std::less and in the end it is automatically sorted.
4. Put your data in a std::vector or std::deque and run std::make_heap() followed by std::pop_heap()-s using std::less.
5. Push your data through a std::priority_queue using std::greater (!!!).

As we can see, std::priority_queue is a definite outlier from such a point of view.

Actually, the reason behind the confusing behavior of std::priority_queue in this regard is hidden in item (4) since that is what a std::priority_queue does underneath. (4) is also against my intuition (though to a lesser extent), since in the intermediate state (while not all std::pop_heap have been performed) the sorted part of the sequence is in its upper range, rather than the lower range.

But it also explains why a max heap was selected for the standard library - std::pop_heap puts the popped element in the location, from where it can be removed in constant time, regardless of the container type used.

what are the constraints for std::ranges::make_heap?

std::ranges::make_heap uses std::ranges::less, which has a constraint:

Unlike std::less, std::ranges::less requires all six comparison operators <, <=, >, >=, == and != to be valid (via the totally_ordered_with constraint).

Your type S does not have an equality operator; the spaceship operator only provides the other comparison operators.*

To fix this, provide an operator== for your type:

constexpr auto operator==(const S& s) const {
  return i == s.i;
}

Godbolt Link: https://godbolt.org/z/cGfrxs

* operator<=> does not imply operator== for performance reasons, as operator== can short circuit over collections whereas operator<=> cannot. However, from https://en.cppreference.com/w/cpp/language/default_comparisons , we see that a defaulted operator<=> will also implicitly default an operator==.

---

How did I figure this out? The error message for your code includes the following (trimmed and word wrapped by me):

note: the expression 'is_invocable_v<_Fn, _Args ...>
    [with _Fn = std::ranges::less&; _Args = {value_type&, value_type&}]'
    evaluated to 'false'
  338 |     concept invocable = is_invocable_v<_Fn, _Args...>;
      |                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This means that std::ranges::make_heap finds that it can't call std::ranges::less for our type. Repeating this error message investigation for std::ranges::less on the value_type of the vector yields:

note: no operand of the disjunction is satisfied
  123 |       requires totally_ordered_with<_Tp, _Up>
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  124 |         || __detail::__less_builtin_ptr_cmp<_Tp, _Up>

At this point, the compiler is trying hard to tell us that we aren't satisfying totally_ordered_with, which means that it's time to hit the documentation for the concept and for std::ranges::less.

Is std::push_heap working for O(n) complexity instead of O(logN) in this case?

You are asking the wrong question. Instead of asking for time complexity you should ask whether what you are doing is well defined behavior.

Answer:
push_heap has the precondition that the range you pass it is a valid heap. More precisely, if you give it the range [first, last[, only [first, last-1[ is required to be a heap and the element at last-1 will be inserted. So if this precondition is not met, the behavior is undefined (and this is the case with push_heap as with any other STL algorithms as far as I know). But if the precondition is met, you are guaranteed to get O(log N) here.

In your example the heap is still valid, because you are changing the last element (which is not required to be part of the heap), so the complexity stays O(log N). If it were no heap anymore, in theory, anything could happen: Crash, O(n), O(2^n), nose dragons.

In practice, however, the complexity will stay at O(log N) because the new entry will still sift through at max O(log N) heap layers, even if one of them is incorrect and sifting stops incorrectly (actually, if the heap is incorrect in the first place, there cannot be "correct" sifting).

How to use make_heap to create a min heap in c++

myComp is a type name, while std::make_heap is a function (template), and to call it you need to pass an object. So create an object of that type.

make_heap(Q.begin(), Q.end(), myComp{});

The {} will initialize the myComp object that you pass.

When you read the documentation Compare is the deduced type of the functor, but note that the function template expects a comp function parameter, that's your object.

---

Related Topics