C++ Heap Sort In C++14 Realized I have never implemented heap sort.

So here is my first attempt:

#include &lt;iterator&gt;
#include &lt;tuple&gt;

/*
0   =&gt; 1 2
1   =&gt; 3 4
2   =&gt; 5 6
3   =&gt; 7 8
4   =&gt; 9 10
5   =&gt; 11 12
6   =&gt; 13 14

P   =&gt; P*2 + 1, P*2 + 2
C   =&gt; (C-1)/2
*/

template&lt;typename I&gt;
class HeapSorter
{
    I getParent(I root, I child)
    {   
        std::size_t dist = std::distance(root, child);
        return root + (dist - 1) / 2;
    }   

    std::tuple&lt;I, I&gt;  getChildren(I root, I parent)
    {   
        std::size_t dist = std::distance(root, parent);
        I left  = root + (dist * 2 + 1); 
        I right = root + (dist * 2 + 2); 
        return {left, right};
    }   

    bool swapLargestValueWithRoot(I&amp; root, I left, I right)
    {   
        using std::swap;
        if (*root &gt;= *left &amp;&amp; *root &gt;= *right) {
            return true;
        }   
        I&amp; swapSrc = (*left &gt;= *right) ? left : right;

        swap(*root, *swapSrc);
        root = swapSrc;
        return false;
    }   

    void siftDown(I root, I begin, I end)
    {   
        I parent    = begin;
        I left;
        I right;
        std::tie(left, right) = getChildren(root, parent);
        while(left &lt; end) {

            if (swapLargestValueWithRoot(parent, left, right == end ? left : right)) {
                break;
            }   
            std::tie(left, right) = getChildren(root, parent);
        }   
    }   

    void heapify(I begin, I end)
    {   
        I child   = end - 1;
        if (child == begin) {
            return;
        }   
        I parent  = getParent(begin, child);
        for(;parent != begin;--parent) {
            siftDown(begin, parent, end);
        }   
        siftDown(begin, begin, end);
    }   
    public:
        void operator()(I begin, I end)
        {   
            static_assert(std::is_same&lt;typename std::iterator_traits&lt;I&gt;::iterator_category, std::random_access_iterator_tag&gt;::value, "For efficiency; Only support random access Iterator");
            if (begin == end) {
                return;
            }   
            heapify(begin, end);
            for(auto loop = end - 1;loop != begin; --loop) {
                std::iter_swap(begin, loop);
                siftDown(begin, begin, loop);
            }   
        }   
};

template&lt;typename I&gt;
void heapSort(I begin, I end)
{
    HeapSorter&lt;I&gt;  sorter;
    sorter(begin, end);
}


Usage Example:

#include &lt;algorithm&gt;
#include &lt;iostream&gt;

int main()
{
    int data[] = { 5,6,3,8,9,1,4,0,2,3,6,1,7,8,9};

    heapSort(std::begin(data), std::end(data));

    std::copy(std::begin(data), std::end(data),
              std::ostream_iterator&lt;int&gt;(std::cout, ","));
}
Well, strictly speaking your code has UB because getChildren(...) tries to create iterators to both child-nodes, even if they are beyond the end-iterator.
Some iterators and containers are more forgiving than others, as are implementations generally...

You forgot the include for std::swap and std::iter_swap: &lt;algorithm&gt;.
Also for std::is_same: &lt;type_traits&gt;.
Both obviously happen to be included by your current includes.

You might want to use std::iter_swap consistently, look in swapLargestValueWithRoot.