Graph/BinaryHeap/BinaryHeap.h

Go to the documentation of this file.
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_ */
Algorithm Development Kit 1.0