maxHeap Class Reference

#include <heap.h>

List of all members.

Public Member Functions

 maxHeap (int size)
 ~maxHeap ()
int numElements ()
int insert (InfoRecord *)
InfoRecorddeleteMax ()
InfoRecorditerator (heapIterator *)
InfoRecordnext (heapIterator *)


Detailed Description

Definition at line 43 of file heap.h.


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, and InfoRecord::load.

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 x.

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 Thu Nov 23 01:17:18 2017 for NAMD by  doxygen 1.4.7