2
\$\begingroup\$

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, ","));
}
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Nice catch. That is something that I can fix. \$\endgroup\$ Feb 1, 2017 at 16:30
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Interesting. That is an optimization. I'll look into it. But to me this is only an optimization if the code is clearer to read in the end. I am not sure I can pull that off (yet). I'll think about it. \$\endgroup\$ Feb 1, 2017 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.