c++stlheapc++14priority-queue

How to replace top element of heap efficiently withouth re-establishing heap invariant twice?


tl;dr: I'm looking for a C++ replacement of Python's heapq.heapreplace.

I have to process a max-heap (used as a priority queue) in such a way that I pop the top element, subtract an unspecified number and then push that modified element again. I could do this using just pop_heap and push_heap but this does unnecessary work because it has to modify the heap twice, each time re-establishing the heap invariant:

std::vector<unsigned> heap;
// ...
std::pop_heap(heap.begin(), heap.end()); // Re-establishes heap invariant.
decrease(heap.back());
std::push_heap(heap.begin(), heap.end()); // Re-establishes heap invariant again.

An efficient interface could look something like this:

decrease(heap.front()); // Modify in-place.
replace_heap(heap.begin(), heap.end());

Is there some trickery with which I get the STL to do what I want or do I have to write replace_heap myself?


Solution

  • As there are no answers so far, I have written my own replace_heap / heapreplace. The C++ standard does not guarantee how the heap maintained by std::push_heap et al. is implemented (it could theoretically be a ternary instead of a binary heap or even something completely different – although at least g++'s stdlib has an ordinary binary heap) so I have also added an accompanying version of push_heap / heappush. Here it is, in case anyone finds it useful:

    #include <functional> // less
    #include <iterator> // iterator_traits
    #include <utility> // move
    
    template <typename DifferenceT>
    DifferenceT heap_parent(DifferenceT k)
    {
        return (k - 1) / 2;
    }
    
    template <typename DifferenceT>
    DifferenceT heap_left(DifferenceT k)
    {
        return 2 * k + 1;
    }
    
    template<typename RandomIt, typename Compare = std::less<>>
    void heapreplace(RandomIt first, RandomIt last, Compare comp = Compare())
    {
        auto const size = last - first;
        if (size <= 1)
            return;
        typename std::iterator_traits<RandomIt>::difference_type k = 0;
        auto e = std::move(first[k]);
        auto const max_k = heap_parent(size - 1);
        while (k <= max_k) {
            auto max_child = heap_left(k);
            if (max_child < size - 1 && comp(first[max_child], first[max_child + 1]))
                ++max_child; // Go to right sibling.
            if (!comp(e, first[max_child]))
                break;
            first[k] = std::move(first[max_child]);
            k = max_child;
        }
    
        first[k] = std::move(e);
    }
    
    template<typename RandomIt, typename Compare = std::less<>>
    void heappush(RandomIt first, RandomIt last, Compare comp = Compare())
    {
        auto k = last - first - 1; // k = last valid
        auto e = std::move(first[k]);
    
        while (k > 0 && comp(first[heap_parent(k)], e)) {
            first[k] = std::move(first[heap_parent(k)]);
            k = heap_parent(k);
        }
    
        first[k] = std::move(e);
    }
    

    I'm still interested in better solutions / solutions requiring fewer custom code.

    EDIT: I have incorporated the suggestion in the comments by @TemplateRex and @Deduplicator. The use of std::less<> without template arguments requires C++14. If you are stuck on C++11, instead of that you will have to use something like default_compare<RandomIt>, defined like follows (untested):

    template <typename Iter>
    using default_compare = std::less<typename std::iterator_traits<Iter>::value_type>;