heap.C

Go to the documentation of this file.
00001 
00007 class manheap;
00008 class maxHeap;
00009 #include <iostream>
00010 using namespace std;
00011 #include "heap.h"
00012 // Heap of pointers. The field to be compared is:
00013 
00014 minHeap::minHeap(int size)
00015 {
00016   this->size = size;
00017   h = new heapRecord[size];
00018   count = 0;
00019 }
00020 
00021 minHeap::~minHeap() {
00022   delete [] h;
00023 }
00024 
00025 int minHeap::numElements()
00026 {
00027   return count;
00028 }
00029 
00030 int minHeap::insert(InfoRecord *x)
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 }
00056 
00057 InfoRecord *minHeap::deleteMin()
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 }
00093 
00094 InfoRecord *minHeap::iterator(heapIterator *iter){
00095   iter->next = 1;
00096   if (count == 0)
00097     return 0;
00098   return h[0].info;
00099 }
00100 InfoRecord *minHeap::next(heapIterator *iter){
00101   if (iter->next >= count)
00102     return 0;
00103   iter->next += 1;
00104   return h[iter->next - 1].info;
00105 }
00106 
00107 //*****************
00108 
00109 
00110 maxHeap::maxHeap(int size)
00111 {
00112   this->size = size;
00113   h = new heapRecord[size];
00114   count = 0;
00115 }
00116 
00117 maxHeap::~maxHeap() {
00118   delete [] h;
00119 }
00120 
00121 int maxHeap::numElements()
00122 {
00123   return count;
00124 }
00125 
00126 int maxHeap::insert(InfoRecord *x)
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 }
00151 
00152 InfoRecord *maxHeap::deleteMax()
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 }
00187 
00188 
00189 InfoRecord *maxHeap::iterator(heapIterator *iter){
00190   iter->next = 1;
00191   if (count == 0)
00192     return 0;
00193   return h[0].info;
00194 }
00195 
00196 InfoRecord *maxHeap::next(heapIterator *iter){
00197   if (iter->next >= count)
00198     return 0;
00199   iter->next += 1;
00200   return h[iter->next - 1].info;
00201 }

Generated on Mon Nov 20 01:17:12 2017 for NAMD by  doxygen 1.4.7