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 simple loop repeatedly calling std::push_heap(a,++b).
std::pop_heap(a,b) (or its comparator-based version) assumes that the range [a,b) is already a max-heap. It swaps a[0] with b[-1], so that the greatest element is now at the back of the range instead of...
