C++ boost::heap::binomial_heap
//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:
using namespace boost::heap;
int main()
{
binomial_heap<int>bq;//creates a binomial_heap
binomial_heap<int>bq1;
auto handle=bq.push(3);//used to push into elements into binomial heap
bq.push(5);
auto handle1=bq.push(7);
auto handle2=bq.push(9);
bq.update(handle, 1);//changes the value and updates it to the reqiured value using a variable handle
bq.decrease(handle1, 3);//when we already know that handle1 contains a greater value than the element that we are changing it to
bq.increase(handle2, 12);//when we already know that handle2 contains a lower value than the element that we are changing it to
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++)//used to iterate through all elements from high priority elements to low priority elements
{
std::cout << *it << " ";//for printing the elements
}
bq.erase(handle);//to remove the element that handle variable is assigned to from the binomial heap
bq.merge(bq1);//binomial heap bq1 becomes empty and all the elements that were previously there in bq1 moves to bq
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();//works as a destructor for bq binomial heap
bq1.~binomial_heap();
return 0;
}
Output:
elements of bq are:
12 5 3 1
elements of bq now are:
12 9 6 5 4 3
More Articles of Shubham Edappanavar:
| Name | Views | Likes |
|---|---|---|
| C++ Boost Any | 1717 | 10 |
| C++ boost::heap::binomial_heap | 1196 | 10 |
| C++ Boost Scope Exit | 6746 | 8 |
| C++ Boost Bind | 1595 | 6 |
| C++ Boost Compressed Pair | 1370 | 10 |
| C++ Boost Dynamic Bitset | 2958 | 10 |
| C++ boost::heap::priority_queue | 1314 | 10 |
| C++ Program to Implement Hash Tables | 5294 | 9 |
Comments