1
\$\begingroup\$

I've written a heapsort implementation. It's generic: generic comparators and sequences with elements of a generic type.

The implementation (follows closely chapter 6 from Introduction to Algorithms 3rd Edition and) consists of

  1. heapify: establishes the heap property for an element:

    template<typename BiDirIterator, typename Cmp>
    void heapify(BiDirIterator begin, BiDirIterator end,
    typename std::iterator_traits<BiDirIterator>::difference_type i, Cmp cmp)
    {
        const auto dist = std::distance(begin, end);
    
        while (true) {
            auto left = 2 * i + 1;
            auto right = left + 1;
            typename std::iterator_traits<BiDirIterator>::value_type largest;
    
            if (left < dist && cmp(begin[left], begin[i]))
                largest = left;
            else
                largest = i;
            if (right < dist && cmp(begin[right], begin[largest]))
                largest = right;
    
            if (largest == i)
                break;
    
            std::swap(begin[i], begin[largest]);
            i = largest;
        }
    }
    
  2. buildHeap: creates a heap from a permutation:

    template<typename BiDirIterator, typename Cmp>
    void buildHeap(BiDirIterator begin, BiDirIterator end, Cmp cmp)
    {
        for (auto i = std::distance(begin, end) / 2 - 1; i >= 1; --i)
            heapify(begin, end, i, cmp);
        heapify(begin, end, 0, cmp);
    }
    
  3. sort: applies Heapsort to retrieve an ordered sequence from the permutation:

    template<typename BiDirIterator, typename Cmp>
    void sort(BiDirIterator begin, BiDirIterator end, Cmp cmp)
    {
        buildHeap(begin, end, cmp);
        for (auto i = std::distance(begin, end) - 1; i > 0; --i) {
            std::swap(*begin, begin[i]);
            heapify(begin, std::next(begin, i - 1), 0, cmp);
        }
    }
    

Necessary includes are:

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

In action:

#include <iostream>
#include <array>

int main()
{
    std::array<int, 10> perm { 5, 6, 9, 3, 6, 4, 8, 4, 87, 4 };

    heap::sort(perm.begin(), perm.end(), heap::max<int>{});
}

where the heap utilities are put into a separate heap namespace and heap::max is simply

template<typename T> using max = std::greater<T>;

Some questions:

  1. Is it OK to use Cmp as a template parameter? That makes it more generic, but the error messages are way more complicated and point to stuff deep down in the implementation. (Granted, you can't say my implementation is anywhere close to "deep," but this is more of a general question.) Passing a Cmp, where Cmp is some alias for a type, would also be possible but not as generic. std::sort also uses the template parameter, though, so I do so as well.
  2. Is my use of iterators alright? I tried to keep the interface clean with iterators for interaction with standard containers, but the implementation also uses numerical indices when it's more convenient.

  3. heapify is ugly: there's an infinite loop with a break condition and it basically finds the largest element out of three while checking that they are within range (i.e., < dist). I have a feeling this can be beautified both syntactically and semantically. Some hint on that would be appreciated.

  4. The implementation is supposed to work with bidirectional iterators. std::list doesn't work because subscripting is not supported, it's not efficient for std::list, etc. Should I replace subscripting with std::next to make it work on std::list at the cost of performance guarantees? std::list would work, but it might be frickin' slow asymptotically.

\$\endgroup\$
2
\$\begingroup\$

left = 2 * i + 1; for a non-random access iterator this is an operation that is linear with regards to i so it's slow for std::list as well.

Heapify can be adust to not need to std::advance an arbitrary amount by going over the list multiple times:

template<typename BiDirIterator, typename Cmp>
void heapify(BiDirIterator begin, BiDirIterator end, Cmp cmp)
{
    bool changed = false;
    do{
        auto parent = begin;
        auto left = begin == end? end : begin+1;
        auto right = left == end? end : left+1;
        while (left != end) {
            auto largest = left
            if (right != end && cmp(*left, *right))
                largest = right;

            if (cmp(*parent, *largest)){
                std::swap(*parent, *largest);
                changed = true;
            }

            parent = ++parent;
            left = right == end? end : right+1;
            right = left == end? end : left+1;
        }
    }while(changed);
}

This will loop over the data at most O(log n) times and puts the elements in heap order.

However for pulling out the data there is no way to only look at the affected elements in O(log n) time. Which means that you can't sort a linked list with heapsort and still be in O(n log n) time complexity.

Instead to sort a linked list in O(n log n) time you would use merge sort. This requires that you are able to be able to split the list up into separate linked lists in that you can merge. std::list has this functionality with it's splice member function. (It also has a sort member function that will do that built-in)

\$\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.