# Heap update generic algorithms

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.

• 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. – Martin York Dec 23 '15 at 19:56
• 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++. – Ilya Popov Dec 23 '15 at 23:58
• 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. – Ilya Popov Dec 23 '15 at 23:59