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 at the front; and then it swaps a[0] with one of its children in the heap, and so on, "bubbling it down" until the max-heap property is restored. After a call to pop_heap(a,b), the greatest element will be at b[-1] and the range [a, b-1) will have the max-heap property.

std::sort_heap(a,b) (or its comparator-based version) takes a range with the max-heap property and permutes it into sorted order by repeatedly calling std::pop_heap(a, b--).

Using these building blocks, we can implement the classic "heapsort" algorithm. The standard library's std::sort function might reasonably be implemented like this (but in practice it is typically implemented as a hybrid algorithm, such as "introsort"):

    template<class RandomIt>
    void push_heap(RandomIt a, RandomIt b)
    {
      auto child = ((b-1) - a);
      while (child != 0) {
        auto parent = (child - 1) / 2;
        if (a[child] < a[parent]) {
          return; // max-heap property has been restored
        }
        std::iter_swap(a+child, a+parent);
        child = parent;
      }
    }

    template<class RandomIt>
    void pop_heap(RandomIt a, RandomIt b)
    {
      using DistanceT = decltype(b - a);

      std::iter_swap(a, b-1);

      DistanceT parent = 0;
      DistanceT new_heap_size = ((b-1) - a);

      while (true) {
        auto leftchild = 2 * parent + 1;
        auto rightchild = 2 * parent + 2;
        if (leftchild >= new_heap_size) {
          return;
        }
        auto biggerchild = leftchild;
        if (rightchild < new_heap_size && a[leftchild] < a[rightchild]) {
          biggerchild = rightchild;
        }
        if (a[biggerchild] < a[parent]) {
          return; // max-heap property has been restored
        }
        std::iter_swap(a+parent, a+biggerchild);
        parent = biggerchild;
      }
    }

    template<class RandomIt>
    void make_heap(RandomIt a, RandomIt b)
    {
      for (auto it = a; it != b; ) {
        push_heap(a, ++it);
      }
    }

    template<class RandomIt>
    void sort_heap(RandomIt a, RandomIt b)
    {
      for (auto it = b; it != a; --it) {
        pop_heap(a, it);
      }
    }

    template<class RandomIt>
    void sort(RandomIt a, RandomIt b)
    {
      make_heap(a, b);
      sort_heap(a, b);
    }

We'll see another application of push_heap and pop_heap in Chapter 4, The Container Zoo, when we talk about std::priority_queue.