Advertisement
Guest User

Untitled

a guest
Jan 24th, 2016
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. void Heap::removeMin()
  2. {
  3.     if (this->nodesNumber == 0)
  4.     {
  5.         std::cout << "Kopiec jest pusty";
  6.         return;
  7.     }
  8.        
  9.     this->heap[1] = this->heap[this->heap.size() - 1];
  10.     this->heap.pop_back(); //usuwanie ostatniego elementu
  11.     this->nodesNumber--;
  12.  
  13.     //schodzenie w dol i odpowiednie rotacje
  14.  
  15.     int *child, *grandchild, childNumber, grandchildNumber, *tmp;
  16.     int elNumber = 1;
  17.     int maxLevel = this->getLevelOfLastNode();
  18.     int coursesNumber;
  19.     bool isEven = this->isLastNodeEven();
  20.     if (isEven)
  21.     {
  22.         maxLevel--;
  23.     }
  24.        
  25.     else
  26.         coursesNumber = floor(maxLevel / 2);
  27.  
  28.     int next, minId,jMin, jMax;
  29.     int *minimum;
  30.     for (int i = 1; i <= maxLevel-2; i+=2) // i - aktualny poziom
  31.     {
  32.         next = i + 2;
  33.         //szukanie minimalnej niżej
  34.         //minimum = this->heap[pow(2, next - 1)];
  35.         minId = pow(2, next - 1);
  36.         jMin = pow(2, next - 1);
  37.         jMax = pow(2, next);
  38.         //for (int j = pow(2, next - 1); j < pow(2, next); j++)
  39.         for (int j = jMin; j<jMax;j++)
  40.         {
  41.             if (j >= this->nodesNumber)
  42.                 break;
  43.             if (*this->heap[minId] > *this->heap[j])
  44.                 minId = j;
  45.         }
  46.         if (*this->heap[elNumber] > *this->heap[minId])
  47.         {
  48.             //swap elementów
  49.             tmp = this->heap[elNumber];
  50.             this->heap[elNumber] = this->heap[minId];
  51.             this->heap[minId] = tmp;
  52.             elNumber = minId;
  53.         }
  54.     }
  55.     if (isEven)
  56.     {
  57.         //zostaje jeszcze jeden poziom.
  58.         for (int i = pow(2, maxLevel - 1); i < pow(2, maxLevel); i++)
  59.         {
  60.             if (i >= this->nodesNumber)
  61.                 break;
  62.             if (*this->heap[elNumber] > *this->heap[i])
  63.             {
  64.                 tmp = this->heap[elNumber];
  65.                 this->heap[elNumber] = this->heap[i];
  66.                 this->heap[i] = tmp;
  67.                 break;
  68.             }
  69.         }
  70.     }
  71.    
  72.     return;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement