+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;
+
