-template <typename K, typename V>
-class Heap {
- class HeapItem;
- struct compare_PI : binary_function <boost::shared_ptr<HeapItem>, boost::shared_ptr<HeapItem>, bool> {
- bool operator() (boost::shared_ptr<HeapItem> x, boost::shared_ptr<HeapItem> y) const {
- return (x->p_key==y->p_key) ? x->m_i<y->m_i : x->p_key>y->p_key;}
- };
-public:
- typedef typename boost::heap::fibonacci_heap<boost::shared_ptr<HeapItem>, boost::heap::compare<compare_PI > >::handle_type HeapHandle;
- typedef boost::shared_ptr<HeapHandle> HeapHandleSPtr;
-private:
- class HeapItem {
- public:
- HeapItem(K key, V value, int i)
- : p_key(key), p_value(value), m_i(i) {
- }
- K p_key;
- V p_value;
- int m_i;
- HeapHandleSPtr sp_handle;
- };
- boost::heap::fibonacci_heap<boost::shared_ptr<HeapItem>, boost::heap::compare<compare_PI > > m_heap;
-public:
- int m_i;
- Heap() : m_i(0) {}
- HeapHandleSPtr push(K key, V value) {
- boost::shared_ptr<HeapItem> hi(new HeapItem(key, value, m_i++));
- hi->sp_handle = boost::shared_ptr<HeapHandle>(new HeapHandle(m_heap.push(hi)));
- return hi->sp_handle;
- }
- void pop() {
- HeapHandleSPtr hl = m_heap.top()->sp_handle;
- m_heap.pop();
- hl->node_ = NULL;
- }
- void erase(HeapHandleSPtr handle) {
- if (used(handle)) {
- m_heap.erase(*handle);
- handle->node_ = NULL;
- }
- }
- K topKey() {return m_heap.top()->p_key;}
- V topValue() {return m_heap.top()->p_value;}
- int size() {return m_heap.size();}
- bool empty() {return m_heap.empty();}
- bool used(HeapHandleSPtr handle) {return handle && handle->node_!=NULL;}
-};
-
-typedef Heap<double, ActionPtr> ActionHeap;
-
