| 1 | #include <iostream>
|
|---|
| 2 | #include "boost/heap/binomial_heap.hpp"
|
|---|
| 3 | #include "boost/heap/fibonacci_heap.hpp"
|
|---|
| 4 | #include "boost/heap/pairing_heap.hpp"
|
|---|
| 5 | #include "boost/heap/skew_heap.hpp"
|
|---|
| 6 |
|
|---|
| 7 | struct heap_data
|
|---|
| 8 | {
|
|---|
| 9 | int payload;
|
|---|
| 10 |
|
|---|
| 11 | heap_data( const int& x ) : payload( x ){}
|
|---|
| 12 |
|
|---|
| 13 | bool operator<( const heap_data& hd ) const
|
|---|
| 14 | {
|
|---|
| 15 | return payload > hd.payload;
|
|---|
| 16 | }
|
|---|
| 17 |
|
|---|
| 18 | };
|
|---|
| 19 |
|
|---|
| 20 | typedef boost::heap::binomial_heap<heap_data> b_heap_t;
|
|---|
| 21 | typedef boost::heap::pairing_heap<heap_data> p_heap_t;
|
|---|
| 22 | typedef boost::heap::skew_heap<heap_data> s_heap_t;
|
|---|
| 23 | typedef boost::heap::fibonacci_heap<heap_data> f_heap_t;
|
|---|
| 24 |
|
|---|
| 25 | template<typename Heap>
|
|---|
| 26 | void
|
|---|
| 27 | assign_heaps( Heap& pq1, Heap& pq2, Heap& pq3 )
|
|---|
| 28 | {
|
|---|
| 29 |
|
|---|
| 30 | pq1.push(heap_data(2));
|
|---|
| 31 | pq1.push(heap_data(3));
|
|---|
| 32 | pq1.push(heap_data(1));
|
|---|
| 33 |
|
|---|
| 34 | pq2.push(heap_data(3));
|
|---|
| 35 | pq2.push(heap_data(4));
|
|---|
| 36 | pq2.push(heap_data(2));
|
|---|
| 37 |
|
|---|
| 38 | pq3.push(heap_data(4));
|
|---|
| 39 | pq3.push(heap_data(5));
|
|---|
| 40 | pq3.push(heap_data(3));
|
|---|
| 41 |
|
|---|
| 42 | }
|
|---|
| 43 |
|
|---|
| 44 | template<typename Heap>
|
|---|
| 45 | void test1( void )
|
|---|
| 46 | {
|
|---|
| 47 | Heap pq1, pq2, pq3;
|
|---|
| 48 |
|
|---|
| 49 | assign_heaps<Heap>( pq1, pq2, pq3 );
|
|---|
| 50 |
|
|---|
| 51 | pq2.merge( pq1 ); // I would think this would fully clear pq1
|
|---|
| 52 |
|
|---|
| 53 | pq1.merge( pq3 );
|
|---|
| 54 |
|
|---|
| 55 | std::cout << "In test 1, pq1:" << std::endl;
|
|---|
| 56 |
|
|---|
| 57 | // I would expect the following to print 3 4 5 but it prints 1 3 4 5
|
|---|
| 58 | // with the fibonacci heap
|
|---|
| 59 |
|
|---|
| 60 | for(
|
|---|
| 61 | typename Heap::ordered_iterator it = pq1.ordered_begin();
|
|---|
| 62 | it != pq1.ordered_end();
|
|---|
| 63 | it++
|
|---|
| 64 | )
|
|---|
| 65 | {
|
|---|
| 66 | std::cout << (*it).payload << std::endl;
|
|---|
| 67 | }
|
|---|
| 68 | }
|
|---|
| 69 |
|
|---|
| 70 | template<typename Heap>
|
|---|
| 71 | void test2( void )
|
|---|
| 72 | {
|
|---|
| 73 | Heap pq1, pq2, pq3;
|
|---|
| 74 |
|
|---|
| 75 | assign_heaps<Heap>( pq1, pq2, pq3 );
|
|---|
| 76 |
|
|---|
| 77 | pq2.merge( pq1 );
|
|---|
| 78 | pq1.clear();
|
|---|
| 79 |
|
|---|
| 80 | pq1.merge( pq3 );
|
|---|
| 81 |
|
|---|
| 82 | std::cout << "In test 2, pq1:" << std::endl;
|
|---|
| 83 |
|
|---|
| 84 | // The following prints out 3 4 5 as expected in all cases because I
|
|---|
| 85 | // cleared pq1 before merging in pq3.
|
|---|
| 86 |
|
|---|
| 87 | for(
|
|---|
| 88 | typename Heap::ordered_iterator it = pq1.ordered_begin();
|
|---|
| 89 | it != pq1.ordered_end();
|
|---|
| 90 | it++
|
|---|
| 91 | )
|
|---|
| 92 | {
|
|---|
| 93 | std::cout << (*it).payload << std::endl;
|
|---|
| 94 | }
|
|---|
| 95 | }
|
|---|
| 96 |
|
|---|
| 97 | int main(void)
|
|---|
| 98 | {
|
|---|
| 99 |
|
|---|
| 100 | std::cout << std::endl << "Binomial heap:" << std::endl;
|
|---|
| 101 |
|
|---|
| 102 | test1<b_heap_t>();
|
|---|
| 103 |
|
|---|
| 104 | test2<b_heap_t>();
|
|---|
| 105 |
|
|---|
| 106 | std::cout << std::endl << "Pairing heap:" << std::endl;
|
|---|
| 107 |
|
|---|
| 108 | test1<p_heap_t>();
|
|---|
| 109 |
|
|---|
| 110 | test2<p_heap_t>();
|
|---|
| 111 |
|
|---|
| 112 | std::cout << std::endl << "Skew heap:" << std::endl;
|
|---|
| 113 |
|
|---|
| 114 | test1<s_heap_t>();
|
|---|
| 115 |
|
|---|
| 116 | test2<s_heap_t>();
|
|---|
| 117 |
|
|---|
| 118 | std::cout << std::endl << "Fibonacci heap:" << std::endl;
|
|---|
| 119 |
|
|---|
| 120 | test1<f_heap_t>();
|
|---|
| 121 |
|
|---|
| 122 | test2<f_heap_t>();
|
|---|
| 123 |
|
|---|
| 124 | return 0;
|
|---|
| 125 |
|
|---|
| 126 | }
|
|---|
