C++ boost::heap::binomial_heap














































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:
#include <iostream> #include<boost/heap/binomial_heap.hpp> 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




Comments