Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 15th, 2012  |  syntax: None  |  size: 4.02 KB  |  hits: 14  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #ifndef _BHEAP
  2. #define _BHEAP
  3.  
  4. namespace alg{
  5.  
  6.         template<class T, class Equal, class Less> class BHeap{
  7.         private:
  8.                 T* nodes;
  9.                 int max_capcity;
  10.                 int current_size;
  11.  
  12.                 Equal cmp;
  13.                 Less less;
  14.  
  15.                 inline int leftIndex(const int& idx)
  16.                 {
  17.                         return (idx << 1) + 1;
  18.                 }
  19.  
  20.                 inline int rightIndex(const int& idx)
  21.                 {
  22.                         return (idx << 1) + 2;
  23.                 }
  24.  
  25.                 inline int parentIndex(const int& idx)
  26.                 {
  27.                         return (idx - 1) >> 1;
  28.                 }
  29.  
  30.                 bool realloc(const int&);
  31.  
  32.         public:
  33.                 BHeap(const int&);
  34.  
  35.                 ~BHeap(void);
  36.  
  37.                 bool push(T);
  38.  
  39.                 T pop(void);
  40.  
  41.                 void shift(const int&);
  42.  
  43.                 void clear(void);
  44.  
  45.                 int find(const T);
  46.  
  47.                 const T& operator[](const int&) const;
  48.  
  49.                 T& operator[](const int&);
  50.  
  51.                 inline T first(void)           
  52.                 {
  53.                         if(!empty())
  54.                                 return nodes[0];
  55.                         else
  56.                                 return 0;
  57.                 }
  58.  
  59.                 inline bool empty(void)
  60.                 {
  61.                         return !current_size;
  62.                 }
  63.  
  64.                 inline int size(void)
  65.                 {
  66.                         return current_size;
  67.                 }
  68.         };
  69.  
  70.  
  71.         template<class T, class Equal, class Less>
  72.         BHeap<T,Equal,Less>::BHeap(const int& max_capcity)
  73.         {
  74.                 this->max_capcity = max_capcity > 32 ? max_capcity : 32;
  75.                 current_size = 0;
  76.                
  77.                 nodes = new T[this->max_capcity];
  78.         }
  79.  
  80.         template<class T, class Equal, class Less>
  81.         BHeap<T,Equal,Less>::~BHeap(void)
  82.         {
  83.                 if(nodes != 0)
  84.                         delete []nodes;
  85.         }
  86.  
  87.         template<class T, class Equal, class Less>
  88.         void BHeap<T,Equal,Less>::clear(void)
  89.         {
  90.                 if(nodes != 0)
  91.                         delete []nodes;
  92.                
  93.                 nodes = new T[max_capcity];
  94.                 current_size = 0;
  95.         }
  96.  
  97.         template<class T, class Equal, class Less>
  98.         bool BHeap<T,Equal,Less>::push(T val)
  99.         {
  100.                 if(current_size == max_capcity){
  101.                         realloc(max_capcity + (max_capcity >> 1));
  102.                 }
  103.  
  104.                 nodes[++current_size - 1] = val;
  105.  
  106.                 int idx = current_size - 1;
  107.                 while(idx != 0){
  108.                         int parentIdx = parentIndex(idx);
  109.  
  110.                         if(!(less(nodes[parentIdx],nodes[idx]))){
  111.                                 T temporary = nodes[parentIdx];
  112.                                 nodes[parentIdx] = nodes[idx];
  113.                                 nodes[idx] = temporary;
  114.                                 idx = parentIdx;
  115.                         }else
  116.                                 break;
  117.                 }
  118.                 return true;
  119.         }
  120.  
  121.         template<class T, class Equal, class Less>
  122.         T BHeap<T,Equal,Less>::pop(void)
  123.         {
  124.                 if(empty())
  125.                         return T();
  126.  
  127.                 T result = nodes[0];
  128.                 nodes[0] = nodes[current_size - 1];
  129.                 current_size--;
  130.                 if(current_size > 0){
  131.                         int idx = 0;
  132.                        
  133.                         while(true){
  134.                                 int leftIdx = leftIndex(idx);
  135.                                 int rightIdx = rightIndex(idx);
  136.                                 int proot = 0;
  137.  
  138.                                 if(rightIdx >= current_size){
  139.                                         if(leftIdx >= current_size)
  140.                                                 break;
  141.                                         else
  142.                                                 proot = leftIdx;
  143.                                 }else{
  144.                                         if(less(nodes[leftIdx], nodes[rightIdx]))
  145.                                                 proot = leftIdx;
  146.                                         else
  147.                                                 proot = rightIdx;
  148.                                 }
  149.                                 if(!less(nodes[idx],nodes[proot])){
  150.                                         T temporary = nodes[proot];
  151.                                         nodes[proot] = nodes[idx];
  152.                                         nodes[idx] = temporary;
  153.                                         idx = proot;
  154.                                 }else
  155.                                         break;
  156.                         }
  157.                 }
  158.                 return result;
  159.         }
  160.  
  161.         template<class T, class Equal, class Less>
  162.         void BHeap<T,Equal,Less>::shift(const int& idx)
  163.         {
  164.                 int nidx = idx;
  165.                 while(nidx != 0){
  166.                         int parentIdx = parentIndex(nidx);
  167.  
  168.                         if(!less(nodes[parentIdx],nodes[nidx])){
  169.                                 T temporary = nodes[parentIdx];
  170.                                 nodes[parentIdx] = nodes[nidx];
  171.                                 nodes[nidx] = temporary;
  172.                                 nidx = parentIdx;
  173.                         }else
  174.                                 break;
  175.                 }
  176.         }
  177.  
  178.         template<class T, class Equal, class Less>
  179.         bool BHeap<T,Equal,Less>::realloc(const int& new_size)
  180.         {
  181.                 if(new_size <= max_capcity || nodes == 0)
  182.                         return false;
  183.  
  184.                 max_capcity = new_size;
  185.  
  186.                 T* new_nodes = new T[max_capcity];
  187.  
  188.                 if(current_size > 0)
  189.                         for(int i = 0; i < current_size; ++i)
  190.                                 new_nodes[i] = nodes[i];
  191.  
  192.                 delete []nodes;
  193.                 nodes = new_nodes;
  194.  
  195.                 return true;
  196.         }
  197.  
  198.         template<class T, class Equal, class Less>
  199.         int BHeap<T,Equal,Less>::find(const T val)
  200.         {
  201.                 for(int i = 0; i < current_size; ++i)
  202.                         if(cmp(nodes[i],val))
  203.                                 return i;
  204.                 return -1;
  205.         }
  206.  
  207.         template<class T, class Equal, class Less>
  208.         const T& BHeap<T,Equal,Less>::operator[](const int& idx) const
  209.         {
  210.                 return nodes[idx];
  211.         }
  212.  
  213.         template<class T, class Equal, class Less>
  214.         T& BHeap<T,Equal,Less>::operator[](const int& idx)
  215.         {
  216.                 return nodes[idx];
  217.         }
  218.  
  219.  
  220. }
  221.  
  222. #endif
create a new version of this paste RAW Paste Data