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

2 Answers 2

Reset to default
4
\$\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\$ Commented Jun 4, 2016 at 13:37
  • \$\begingroup\$ oops should have used less there aswell. You are right that will be better :). \$\endgroup\$ Commented Jun 4, 2016 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\$ Commented Jun 4, 2016 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\$ Commented Jun 4, 2016 at 18:45
2
\$\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\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.