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\$
  • \$\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\$ – Martin York Dec 23 '15 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 Dec 23 '15 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 Dec 23 '15 at 23:59

Your Answer

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

Browse other questions tagged or ask your own question.