boost::range::sort_heap

References

Headers

boost::range::sort_heap is available by including any of the following headers:

  • boost/range/algorithm/heap_algorithm.hpp or
  • boost/range/algorithm.hpp

Examples

heap.cpp

#include <functional>
#include <iostream>
#include <boost/range/algorithm.hpp>


void display(const std::string &caption, const std::vector<int> vec) {
    std::cout << caption;
    boost::copy(vec, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

int main() {
    std::vector<int> vec = {1, 3, 9, 4, 16, 7};

    // make_heap() turns the input range to a heap. By default, a max-heap
    // is created, but this can be overridden by passing a different ordering
    // predicate.
    // Returns a reference to the input range.
    boost::range::make_heap(vec);
    display("Initial heap: ", vec);

    // pop_heap() rearranges the input range so that [0, end-1) is a new
    // max-heap and rng[end-1] holds the previous max element.
    // Removal of elements from the heap always consists of this
    // pop_heap()/pop_back() cascade.
    // Returns a reference to the input range.
    boost::range::pop_heap(vec);
    vec.pop_back();
    display("Heap after pop_heap(): ", vec);

    // push_heap() takes the element at rng[end-1] and inserts it into a
    // pre-existing heap in [0, end-1). Heap insertion always consists
    // of this push_back/push_heap cascade.
    // Returns a reference to the input range.
    vec.push_back(32);
    boost::range::push_heap(vec);
    display("Heap after push_heap(): ", vec);

    // sort_heap() sorts a pre-existing heap in the input range.
    // This destroys the heap properties.
    boost::range::sort_heap(vec);
    display("Heap after sorting: ", vec);

    return 0;
}

Output:

Initial heap: 16 4 9 1 3 7 
Heap after pop_heap(): 9 4 7 1 3 
Heap after push_heap(): 32 4 9 1 3 7 
Heap after sorting: 1 3 4 7 9 32

 

heap_with_predicate.cpp

#include <functional>
#include <iostream>
#include <boost/range/algorithm.hpp>


void display(const std::string &caption, const std::vector<int> vec) {
    std::cout << caption;
    boost::copy(vec, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

int main() {
    std::vector<int> vec = {1, 3, 9, 4, 16, 7};


    // make_heap() turns the input range to a heap. By default, a max-heap
    // is created, but this can be overridden by passing a different ordering
    // predicate. In this case, a min-heap is generated.
    // Returns a reference to the input range.
    boost::range::make_heap(vec, std::greater<int>());
    display("Initial heap: ", vec);

    // pop_heap() rearranges the input range so that [0, end-1) is a new
    // heap and rng[end-1] holds the previous top element.
    // Removal of elements from the heap always consists of this
    // pop_heap()/pop_back() cascade.
    // Returns a reference to the input range.
    boost::range::pop_heap(vec, std::greater<int>());
    vec.pop_back();
    display("Heap after pop_heap(): ", vec);

    // push_heap() takes the element at rng[end-1] and inserts it into a
    // pre-existing heap in [0, end-1). Heap insertion always consists
    // of this push_back/push_heap cascade.
    // Returns a reference to the input range.
    vec.push_back(32);
    boost::range::push_heap(vec, std::greater<int>());
    display("Heap after push_heap(): ", vec);

    // sort_heap() sorts a pre-existing heap in the input range.
    // This destroys the heap properties.
    boost::range::sort_heap(vec, std::greater<int>());
    display("Heap after sorting: ", vec);

    return 0;
}

Output:

Initial heap: 1 3 7 4 16 9 
Heap after pop_heap(): 3 4 7 9 16 
Heap after push_heap(): 3 4 7 9 16 32 
Heap after sorting: 32 16 9 7 4 3

 

Boost Range for Humans

This reference is part of Boost Range for Humans. Click the link to the overview.