7
\$\begingroup\$

Just checking if I could still do it:

#include <iostream>
#include <algorithm>

std::size_t getParent(std::size_t n)
{
    return (n - 1) / 2;
}

template<typename I>
void heapify(I begin, I end)
{
    std::size_t size    = std::distance(begin, end);
    for(std::size_t loop = 1;loop < size; ++loop)
    {
        std::size_t current = loop;
        std::size_t parent  = getParent(current);
        while(current != 0 && *(begin + parent) < *(begin + current))
        {
            std::swap(*(begin + parent), *(begin + current));
            current = parent;
            parent  = getParent(current);
        }
    }
}

template<typename I>
void heapPop(I begin, I end)
{
    I   last = end - 1;
    std::swap(*begin, *last);

    std::size_t size    = std::distance(begin, last);
    std::size_t current = 0;
    while(current < size)
    {
        std::size_t child1  = current * 2 + 1;
        std::size_t child2  = current * 2 + 2;
        std::size_t goodChild = current;

        if (child2 < size)
        {
            goodChild   = (*(begin + child1) > *(begin + child2)) ? child1 : child2;
        }
        else if (child1 < size)
        {
            goodChild   = child1;
        }
        if (*(begin + current) < *(begin + goodChild))
        {
            std::swap(*(begin + current), *(begin + goodChild));
            current = goodChild;
            continue;
        }
        break;
    }
}


template<typename I>
void heap_sort(I begin, I end)
{
    heapify(begin, end);
    while(begin != end)
    {
        heapPop(begin, end);
        --end;
    }
}

int main()
{
    int  data[] = {6,5,3,1,8,7,2,4};
    heap_sort(std::begin(data), std::end(data));
    std::copy(std::begin(data), std::end(data), std::ostream_iterator<int>(std::cout, ", "));
    std::cout << "\n";
}
\$\endgroup\$
1
3
\$\begingroup\$

The heapify and parentfunctions can be avoided:

You just need the sinking logic that you already implemented. But instead of having current always starting at 0 you can set it as a parameter:

template<typename I>
void sink(I begin, I end, std::size_t index)
{

    std::size_t size = std::distance(begin, end);
    std::size_t current = index;
    while (current < size)
    {
        std::size_t child1 = current * 2 + 1;
        std::size_t child2 = current * 2 + 2;
        std::size_t goodChild = current;

        if (child2 < size)
        {
            goodChild = (*(begin + child1) > *(begin + child2)) ? child1 : child2;
        }
        else if (child1 < size)
        {
            goodChild = child1;
        }
        if (*(begin + current) < *(begin + goodChild))
        {
            std::swap(*(begin + current), *(begin + goodChild));
            current = goodChild;
            continue;
        }
        break;
    }
}

Due to the fact that the elements are leafs you can ignore them, so you just need to apply sink times to build the heap:

template<typename I>
void heap_sort(I begin, I end)
{
    std::size_t size = std::distance(begin, end);
    for (int i = size / 2 - 1; i > -1; --i) 
    {
        sink(begin, end, i);
    }
    while (begin != --end) 
    {
        std::swap(*begin, *end);
        sink(begin, end, 0);
    }
}

Alternative sink implementation:

IMO this implementation is more concise:

template<typename I>
void sink(I begin, I end, std::size_t index)
{

    std::size_t size = std::distance(begin, end);
    std::size_t current = index;
    std::size_t child;

    std::less<decltype(*begin)> less;

    while ((child = 2 * current + 1) < size)
    {
        I itr_child   = begin + child;
        I itr_current = begin + current;

        if(child < size - 1 
            && less(*itr_child, *(itr_child + 1))
        {
            ++itr_child;
        }

        if (!less(*itr_current, *itr_child))
        {
            break;
        }
        std::swap(*itr_current, *itr_child);
        current = child;
    }
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ alternative sink function is much better, i have only one suggestion, if you changed *(itr_child + 1) > *itr_child to some thing like!Pred(*(itr_child + 1), *itr_child), it will allow the user to define his predicative expressions in template parameters. i have modified your sink function to be recursive with default predicate std::less. live demo cpp.sh/636i \$\endgroup\$ – MORTAL Jun 4 '16 at 13:37
  • \$\begingroup\$ oops should have used less there aswell. You are right that will be better :). \$\endgroup\$ – MAG Jun 4 '16 at 16:33
  • \$\begingroup\$ Nice alternate solution, but assignment in expression (child = 2 * current + 1) is bound to always raise the question: "was that really the intention or did they mean ==". I would personally avoid that. \$\endgroup\$ – glampert Jun 4 '16 at 18:30
  • \$\begingroup\$ @glampert You got a point there, I guess the trade of readability for conciseness is not really worth it in that case. \$\endgroup\$ – MAG Jun 4 '16 at 18:45
1
\$\begingroup\$

i inspired of @MAG alternative solution, i re-implemented it in recursive way by providing template parameters. as following:

template <typename RandomAccessIterator, typename Distance, typename Compare>
void adjust_heap(RandomAccessIterator first, Distance len, Distance current, Compare comp)
{
    if(current >= len) return;

    Distance child = current * 2 + 1;

    if (child >= len) return;

    if ((child + 1 < len) && !comp(first[child + 1], first[child]))
        child++;

    if (!comp(first[current], first[child])) return;

    std::swap(first[current], first[child]);

    adjust_heap(first, len, child, comp);
}

for sort the heap. first we need to make the heap and then sort it like so:

template <typename RandomAccessIterator, typename Compare =
std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>>
void heap_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp = Compare{})
{
    using Distance = typename std::iterator_traits<RandomAccessIterator>::difference_type;

    // make heap
    const Distance size = last - first;
    for (Distance i = size / 2 - 1; i >= 0; --i)
    {
        adjust_heap(first, size, i, comp);
    }

    // sort heap
    for (Distance i = size - 1; i > 0; --i)
    {
        std::swap(first[0], first[i]);
        adjust_heap(first, i, Distance(0), comp);
    }
}

code:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <functional>

template <typename RandomAccessIterator, typename Distance, typename Compare>
void adjust_heap(RandomAccessIterator first, Distance len, Distance current, Compare comp)
{
    if (current >= len) return;

    Distance child = current * 2 + 1;

    if (child >= len) return;

    if ((child + 1 < len) && !comp(first[child + 1], first[child]))
        child++;

    if (!comp(first[current], first[child])) return;

    std::swap(first[current], first[child]);

    adjust_heap(first, len, child, comp);
}

template <typename RandomAccessIterator, typename Compare =
std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>>
void heap_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp = Compare{})
{
    using Distance = typename std::iterator_traits<RandomAccessIterator>::difference_type;

    // make heap
    const Distance size = last - first;
    for (Distance i = size / 2 - 1; i >= 0; --i)
    {
        adjust_heap(first, size, i, comp);
    }

    // sort heap
    for (Distance i = size - 1; i > 0; --i)
    {
        std::swap(first[0], first[i]);
        adjust_heap(first, i, Distance(0), comp);
    }
}

int main()
{
    int  data[] = {6,5,3,1,8,7,2,4};
    std::copy(std::begin(data), std::end(data), std::ostream_iterator<int>(std::cout, ", "));
    std::cout << "\n";

    heap_sort(std::begin(data), std::end(data));
    std::copy(std::begin(data), std::end(data), std::ostream_iterator<int>(std::cout, ", "));
    std::cout << "\n";

    heap_sort(std::begin(data), std::end(data), std::greater<int>());
    std::copy(std::begin(data), std::end(data), std::ostream_iterator<int>(std::cout, ", "));
    std::cout << "\n";
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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