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

minHeap Class Reference

#include <heap.h>

List of all members.

Public Member Functions

 minHeap (int size)
 ~minHeap ()
int numElements ()
int insert (InfoRecord *)
InfoRecord * deleteMin ()
InfoRecord * iterator (heapIterator *)
InfoRecord * next (heapIterator *)

Constructor & Destructor Documentation

minHeap::minHeap (  int  size  ) 
 

Definition at line 14 of file heap.C.

00015 {
00016   this->size = size;
00017   h = new heapRecord[size];
00018   count = 0;
00019 }

minHeap::~minHeap (   ) 
 

Definition at line 21 of file heap.C.

00021                   {
00022   delete [] h;
00023 }

Member Function Documentation

InfoRecord * minHeap::deleteMin (   ) 
 

Definition at line 57 of file heap.C.

References heapRecord::info, and InfoRecord::load.

00058 {
00059   if (count == 0) return 0;
00060 
00061   InfoRecord *tmp = h[0].info;
00062   int best;
00063 
00064   h[0] = h[count-1];
00065   count--;
00066 
00067   int current = 0;
00068   int c1 = 1;
00069   int c2 = 2;
00070   while (c1 < count)
00071     {
00072       if (c2 >= count)
00073         best = c1;
00074       else
00075         {
00076           if (h[c1].info->load < h[c2].info->load)
00077             best = c1;
00078           else
00079             best = c2;
00080         }
00081       if (h[best].info->load < h[current].info->load)
00082         {
00083           swap(best, current);
00084           current = best;
00085           c1 = 2*current + 1;
00086           c2 = c1 + 1;
00087         }
00088       else
00089         break;
00090     }
00091   return tmp;
00092 }

int minHeap::insert (  InfoRecord *   ) 
 

Definition at line 30 of file heap.C.

References heapRecord::deleted, heapRecord::info, and InfoRecord::load.

Referenced by Rebalancer::makeHeaps(), and Rebalancer::makeTwoHeaps().

00031 {
00032   h[count].info = x;
00033   h[count].deleted = 0;
00034 
00035   int current = count;
00036   count++;
00037 
00038   if (count >= size) {
00039     std::cout << "minHeap overflow. \n" ; 
00040     return -1;}
00041 
00042   int parent = (current - 1)/2;
00043   while (current != 0)
00044     {
00045       if (h[current].info->load < h[parent].info->load)
00046         {
00047           swap(current, parent);
00048           current = parent;
00049           parent = (current-1)/2;
00050         }
00051       else
00052         break;
00053     }
00054   return 0;
00055 }

InfoRecord * minHeap::iterator (  heapIterator *   ) 
 

Definition at line 94 of file heap.C.

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

00094                                                {
00095   iter->next = 1;
00096   if (count == 0)
00097     return 0;
00098   return h[0].info;
00099 }

InfoRecord * minHeap::next (  heapIterator *   ) 
 

Definition at line 100 of file heap.C.

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

00100                                            {
00101   if (iter->next >= count)
00102     return 0;
00103   iter->next += 1;
00104   return h[iter->next - 1].info;
00105 }

int minHeap::numElements (   ) 
 

Definition at line 25 of file heap.C.

00026 {
00027   return count;
00028 }

The documentation for this class was generated from the following files:
Generated on Mon Oct 13 04:07:46 2008 for NAMD by  doxygen 1.3.9.1