4
\$\begingroup\$

In the standard library, there are no algorithms for element updates. This makes it unsuitable as a queue for a Dijkstra's algorithm, for example. Thus I implemented generic heap update functions with the interface in line with the standard library.

Warning: the standard does not specify implementation detail of a heap. This code assumes a binary max heap. This assumption is true for libstdc++ and libc++, and probably most other implementations of standard library. Having sift_up and sift_down it is trivial to implement other heap algorithms.

template <typename RandomAccessIterator, typename Comparator = 
         std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>>
void sift_up(RandomAccessIterator first, RandomAccessIterator last,
             RandomAccessIterator pos, Comparator && cmp = Comparator())
{
    (void) last; // suppress a warning about unused parameter
    using std::iter_swap;

    while (pos != first)
    {
        auto parent = first + (pos - first - 1) / 2;
        if (!cmp(*parent, *pos))
            break;
        iter_swap(parent, pos);
        pos = parent;
    }
}

template <typename RandomAccessIterator, typename Comparator = 
          std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>>
void sift_down(RandomAccessIterator first, RandomAccessIterator last, 
               RandomAccessIterator pos, Comparator && cmp = Comparator())
{
    using std::iter_swap;

    while (true)
    {
        auto max_child = first + 2*(pos - first) + 1;
        if (!(max_child < last))
            break;
        if (max_child + 1 < last && cmp(*max_child, *(max_child+1)))
            ++max_child;

        if (!cmp(*pos, *max_child))
            break;
        iter_swap(pos, max_child);
        pos = max_child;
    }
}

Edit: added a remark about implementation detail of a heap being unspecified in the standard.

\$\endgroup\$
3
  • \$\begingroup\$ You are going to have to provide a detailed comment to prove you are bot breaking the invariant of a heap. Which I don't think you can as I am not sure they are specified. \$\endgroup\$ Commented Dec 23, 2015 at 19:56
  • \$\begingroup\$ Yes, indeed, the standard does not specify any implementation detail of a heap. This assumes that it is a binary max heap, as it is in listdc++ and libc++. \$\endgroup\$
    – Ilya Popov
    Commented Dec 23, 2015 at 23:58
  • \$\begingroup\$ But having sift_up and sift_down it is trivial to implement push_heap and pop_heap to make a complete independent implementation of the heap. \$\endgroup\$
    – Ilya Popov
    Commented Dec 23, 2015 at 23:59

0

Your Answer

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

Browse other questions tagged or ask your own question.