Realized I have never implemented heap sort.So here is my first attempt:#include <iterator>#include <tuple>/*0   => 1 21   => 3 42   => 5 63   => 7 84   => 9 105   => 11 126   => 13 14P   => P*2 + 1, P*2 + 2C   => (C-1)/2*/template<typename I>class HeapSorter{    I getParent(I root, I child)    {           std::size_t dist = std::distance(root, child);        return root + (dist - 1) / 2;    }       std::tuple<I, I>  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& root, I left, I right)    {           using std::swap;        if (*root >= *left && *root >= *right) {            return true;        }           I& swapSrc = (*left >= *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 < 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<typename std::iterator_traits<I>::iterator_category, std::random_access_iterator_tag>::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<typename I>void heapSort(I begin, I end){    HeapSorter<I>  sorter;    sorter(begin, end);}Usage Example:#include <algorithm>#include <iostream>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<int>(std::cout, ,));}
C++ Heap Sort In C++14
c++;heap sort
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: <algorithm>.Also for std::is_same: <type_traits>.Both obviously happen to be included by your current includes.You might want to use std::iter_swap consistently, look in swapLargestValueWithRoot.