00001 00012 #ifndef _BHEAP_H_ 00013 #define _BHEAP_H_ 00014 00015 #ifdef REPORT 00016 00017 #define INC_SMALL _numSmallest++ 00018 00019 #define INC_COMP _numComparisons++ 00020 00021 #define INC_SWAP _numSwaps++ 00022 00023 #define INC_INSERT _numInsert++ 00024 00025 #define INC_DECREASE _numDecrease++ 00026 #else 00027 #define INC_INSERT 00028 #define INC_SMALL 00029 #define INC_COMP 00030 #define INC_SWAP 00031 #define INC_DECREASE 00032 #endif /* REPORT */ 00033 00037 typedef struct elt { 00038 00040 int id; 00041 00043 int priority; 00044 } ELEMENT, *ELEMENT_PTR; 00045 00049 class BinaryHeap { 00050 00051 public: 00052 BinaryHeap (int); 00053 ~BinaryHeap (); 00054 00055 bool isEmpty() { return (_n == 0); } 00056 int smallest(); 00057 void insert (int, int); 00058 void decreaseKey (int, int); 00059 00060 private: 00061 int _n; // number of elements in binary heap 00062 ELEMENT_PTR _elements; // values in the heap 00063 int *_pos; // pos[i] is index into elements for ith value 00064 00065 long _numComparisons; 00066 long _numInsert; 00067 long _numSwaps; 00068 long _numSmallest; 00069 long _numDecrease; 00070 00071 }; 00072 00073 #endif /* _BHEAP_H_ */