Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void Heap::removeMin()
- {
- if (this->nodesNumber == 0)
- {
- std::cout << "Kopiec jest pusty";
- return;
- }
- this->heap[1] = this->heap[this->heap.size() - 1];
- this->heap.pop_back(); //usuwanie ostatniego elementu
- this->nodesNumber--;
- //schodzenie w dol i odpowiednie rotacje
- int *child, *grandchild, childNumber, grandchildNumber, *tmp;
- int elNumber = 1;
- int maxLevel = this->getLevelOfLastNode();
- int coursesNumber;
- bool isEven = this->isLastNodeEven();
- if (isEven)
- {
- maxLevel--;
- }
- else
- coursesNumber = floor(maxLevel / 2);
- int next, minId,jMin, jMax;
- int *minimum;
- for (int i = 1; i <= maxLevel-2; i+=2) // i - aktualny poziom
- {
- next = i + 2;
- //szukanie minimalnej niżej
- //minimum = this->heap[pow(2, next - 1)];
- minId = pow(2, next - 1);
- jMin = pow(2, next - 1);
- jMax = pow(2, next);
- //for (int j = pow(2, next - 1); j < pow(2, next); j++)
- for (int j = jMin; j<jMax;j++)
- {
- if (j >= this->nodesNumber)
- break;
- if (*this->heap[minId] > *this->heap[j])
- minId = j;
- }
- if (*this->heap[elNumber] > *this->heap[minId])
- {
- //swap elementów
- tmp = this->heap[elNumber];
- this->heap[elNumber] = this->heap[minId];
- this->heap[minId] = tmp;
- elNumber = minId;
- }
- }
- if (isEven)
- {
- //zostaje jeszcze jeden poziom.
- for (int i = pow(2, maxLevel - 1); i < pow(2, maxLevel); i++)
- {
- if (i >= this->nodesNumber)
- break;
- if (*this->heap[elNumber] > *this->heap[i])
- {
- tmp = this->heap[elNumber];
- this->heap[elNumber] = this->heap[i];
- this->heap[i] = tmp;
- break;
- }
- }
- }
- return;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement