Mastering the C++17 STL

Heaps and heapsort

std::make_heap(a,b) (or its comparator-based version, std::make_heap(a,b,cmp)) takes a range of unsorted elements and rearranges them into an order that satisfies the max-heap property: in an array with the max-heap property, each element of the range at index i will be at least as great as either of the elements at indices 2i+1 and 2i+2. This implies that the greatest element of all will be at index 0.

std::push_heap(a,b) (or its comparator-based version) assumes that the range [a,b-1) is already a max-heap. It takes the element currently at b[-1] and "bubbles it up," by swapping with its parent in the heap, until the max-heap property is restored for the whole range [a,b). Notice that make_heap can be implemented as a ...