//Implementable on C++ 11/14/17
Boost::heap::binomial_heap
Description:
In addition to all the functions and properties that boost::heap::priority_queue provides, these have even more benefits like merging 2 priority queues, changing an element at a specific position, and many more useful functions.
There are more heaps like fibonacci_heap, skew_heap, pairing_heap, d_ary_heap but all provide just the same functionality as binomial_heap does, except they differ in performance/time complexity for specific member function. Example-for push() function binomial_heap has logarithmic time complexity whereas that of fibonacci_heap is constant.
Header File Used:
#include<boost/heap/binomial_heap.hpp>
Function:
In addition to all the functions that boost::heap::priority_queue provides, boost::heap::binomial_heap provides some more important functions which are listed below:-
>decrease():- updates the heap after the element handled by \c handle has been changed. This is used when we know in advance whether a change will result in a lower priority.
>increase():- updates the heap after the element handled by \c handle has been changed. This is used when we know in advance whether a change will result in a higher priority.
>erase():- removes the element handled by \c handle from the priority_queue.
>merge():- merge with priority_queue RHS, is basically used to merge two priority_queue.
>update():- updates the heap after the element handled by \c handle has been changed.
>ordered_begin():- returns an iterator referring to the first element according to the highest priority, generally used for printing elements in sorted order.
>ordered_end():- returns an iterator referring to the last element according to the highest priority, generally used for printing elements in sorted order.
>~binomial_heap():- destructor to a binomial_heap.
Program demonstrating the functions:
#include <iostream>
#include<boost/heap/binomial_heap.hpp>
using namespace boost::heap;
int main()
{
binomial_heap<int>bq;
binomial_heap<int>bq1;
auto handle=bq.push(3);
bq.push(5);
auto handle1=bq.push(7);
auto handle2=bq.push(9);
bq.update(handle, 1);
bq.decrease(handle1, 3);
bq.increase(handle2, 12);
bq1.push(4);
bq1.push(9);
bq1.push(6);
std::cout << "elements of bq are:\n";
for (auto it = bq.ordered_begin();it != bq.ordered_end();it++)
{
std::cout << *it << " ";
}
bq.erase(handle);
bq.merge(bq1);
std::cout << "\nelements of bq now are:\n";
for (auto it = bq.ordered_begin();it != bq.ordered_end();it++)
{
std::cout << *it << " ";
}
bq.~binomial_heap();
bq1.~binomial_heap();
return 0;
}
elements of bq are:
12 5 3 1
elements of bq now are:
12 9 6 5 4 3
Comments