Heapsort With Full-Scale Genericity
left = 2 * i + 1; for a non-random access iterator this is an operation that is linear with regards to i so it's slow for std::list as well.

Heapify can be adust to not need to std::advance an arbitrary amount by going over the list multiple times:

template&lt;typename BiDirIterator, typename Cmp&gt;
void heapify(BiDirIterator begin, BiDirIterator end, Cmp cmp)
{
    bool changed = false;
    do{
        auto parent = begin;
        auto left = begin == end? end : begin+1;
        auto right = left == end? end : left+1;
        while (left != end) {
            auto largest = left
            if (right != end &amp;&amp; cmp(*left, *right))
                largest = right;

            if (cmp(*parent, *largest)){
                std::swap(*parent, *largest);
                changed = true;
            }

            parent = ++parent;
            left = right == end? end : right+1;
            right = left == end? end : left+1;
        }
    }while(changed);
}


This will loop over the data at most O(log n) times and puts the elements in heap order.

However for pulling out the data there is no way to only look at the affected elements in O(log n) time. Which means that you can't sort a linked list with heapsort and still be in O(n log n) time complexity. 

Instead to sort a linked list in O(n log n) time you would use merge sort. This requires that you are able to be able to split the list up into separate linked lists in that you can merge. std::list has this functionality with it's splice member function. (It also has a sort member function that will do that built-in)