Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

maxHeap Class Reference

#include <heap.h>

List of all members.

Public Member Functions

 maxHeap (int size)
 ~maxHeap ()
int numElements ()
int insert (InfoRecord *)
InfoRecord * deleteMax ()
InfoRecord * iterator (heapIterator *)
InfoRecord * next (heapIterator *)

Constructor & Destructor Documentation

maxHeap::maxHeap (  int  size  ) 
 

Definition at line 110 of file heap.C.

00111 {
00112   this->size = size;
00113   h = new heapRecord[size];
00114   count = 0;
00115 }

maxHeap::~maxHeap (   ) 
 

Definition at line 117 of file heap.C.

00117                   {
00118   delete [] h;
00119 }

Member Function Documentation

InfoRecord * maxHeap::deleteMax (   ) 
 

Definition at line 152 of file heap.C.

References heapRecord::info, InfoRecord::load, and msm::swap().

Referenced by RefineTorusLB::newRefine(), and Rebalancer::refine().

00153 {
00154   if (count == 0) return 0;
00155   InfoRecord *tmp = h[0].info;
00156   int best;
00157 
00158   h[0] = h[count-1];
00159   count--;
00160 
00161   int current = 0;
00162   int c1 = 1;
00163   int c2 = 2;
00164   while (c1 < count)
00165     {
00166       if (c2 >= count)
00167         best = c1;
00168       else
00169         {
00170           if (h[c1].info->load > h[c2].info->load)
00171             best = c1;
00172           else
00173             best = c2;
00174         }
00175       if (h[best].info->load > h[current].info->load)
00176         {
00177           swap(best, current);
00178           current = best;
00179           c1 = 2*current + 1;
00180           c2 = c1 + 1;
00181         }
00182       else
00183         break;
00184     }
00185   return tmp;
00186 }

int maxHeap::insert (  InfoRecord *   ) 
 

Definition at line 126 of file heap.C.

References heapRecord::deleted, heapRecord::info, InfoRecord::load, and msm::swap().

Referenced by Rebalancer::makeHeaps(), Rebalancer::makeTwoHeaps(), RefineTorusLB::newRefine(), and Rebalancer::refine().

00127 {
00128   h[count].info = x;
00129   h[count].deleted  = 0;
00130   int current = count;
00131   count++;
00132 
00133   if (count >= size) {
00134     std::cout << "maxHeap overflow. \n" ; 
00135     return -1;}
00136 
00137   int parent = (current - 1)/2;
00138   while (current != 0)
00139     {
00140       if (h[current].info->load > h[parent].info->load)
00141         {
00142           swap(current, parent);
00143           current = parent;
00144           parent = (current-1)/2;
00145         }
00146       else
00147         break;
00148     }
00149   return 0;
00150 }

InfoRecord * maxHeap::iterator (  heapIterator *   ) 
 

Definition at line 189 of file heap.C.

References heapRecord::info, and heapIterator::next.

00189                                                {
00190   iter->next = 1;
00191   if (count == 0)
00192     return 0;
00193   return h[0].info;
00194 }

InfoRecord * maxHeap::next (  heapIterator *   ) 
 

Definition at line 196 of file heap.C.

References heapRecord::info, and heapIterator::next.

00196                                            {
00197   if (iter->next >= count)
00198     return 0;
00199   iter->next += 1;
00200   return h[iter->next - 1].info;
00201 }

int maxHeap::numElements (   ) 
 

Definition at line 121 of file heap.C.

00122 {
00123   return count;
00124 }

The documentation for this class was generated from the following files:
Generated on Wed May 22 04:07:24 2013 for NAMD by  doxygen 1.3.9.1