Kopiec minimaksowy - usuwanie elementu

0

Witam.
Dostałem za zadanie napisanie kopca minimaksowego. Dodawanie zrobiłem, nawet działa. przyszedł czas na usuwanie minimalnego elementu. Napisałem kod i niestety nie chce to działać. Po ~2 przebiegach na górę lecą wcale nie najmniejsze elementy, a z czasem jeszcze bardziej się to pogłębia. Wie ktoś może co tutaj jest źle?

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;
} 
0

Tego raczej się nie zauważa patrząc na kod, tylko trzeba debuggować.

0
twonek napisał(a):

Tego raczej się nie zauważa patrząc na kod, tylko trzeba debuggować.

Problem w tym, że debugger już tutaj nie pomaga. Domyślam się (jestem praktycznie pewien), że to jest wina błędnego algorytmu usuwania. Niestety w internecie zwyczajnie nie ma żadnego opisanego po ludzku. Jeśli już coś się trafi to jest to pseudokod z wykorzystaniem jakichś funkcji, które też nie są opisane, a bez nich nic się nie ugra...

1 użytkowników online, w tym zalogowanych: 0, gości: 1