C++ Heap Sort In C++14

Question

Realized I have never implemented heap sort.

So here is my first attempt:

#include <iterator>
#include <tuple>

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

P   => P*2 + 1, P*2 + 2
C   => (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, ","));
}

Answer 1

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.

Answer 2

I am not in position to review your code as is, since your C++ is better than mine, yet I would outline a minor optimization opportunity: whenever sifting, say, upwards, you basically start from element \$u_1\$, swap with \$u_2\$, and so on until you reach the element \$u_n\$ which maintains the heap invariant. In your implementation, you make \$3(n - 1)\$ assignments in order to restore the invariant. What you could do is to, instead, shift \$u_2\$ to the position of \$u_1\$, \$u_3\$ to \$u_2\$ and so on until \$u_n\$. Last, you just assign the key of \$u_1\$ to \$u_n\$ in total of \$n\$ assignments.

Hope that helps.