left와 right관련 질문입니다.

힙이 완전이진트리이기 때문에

왼쪽을 먼저 비교하여 진행하게 알고리즘을 만드는것까지는 이해했습니다.

그런데 왼쪽을 통과 했을 경우에도 우측을 한번 더 비교하는 이유가 따로 있는건지 궁금합니다.

-> less기준 으로 부모가 자식노드보다 크기만 하면 되는것이 아닌가 궁금합니다. 지금 코드로 하게 되면 왼쪽과 오른쪽 둘다 부모노드보다 클 경우 우측이랑 교환을 하게 되는데, 코드가 복잡해져서 굳이 처리를 안하는걸까요?

else if 를 사용하지 않는 이유가 있을까요?

void pop() 
{
	_heap[0] = _heap.back();
	_heap.pop_back();

	int now = 0;

	while (true) 
	{
		int left = now * 2 + 1;
		int right = now * 2 + 2;

		if (_heap.size() <= left) break;

		int next = now;
		if (_heap[next] < _heap[left]) next = left;
		else if (_heap.size() > right && _heap[next] < _heap[right]) next = right;

		if (next == now) break;

		::swap(_heap[next], _heap[now]);
		now = next;
	}
}

안녕하세요, 인프런 AI 인턴입니다.

왼쪽 자식과의 비교를 통과한 후 여전히 오른쪽 자식과 비교하는 이유는, 힙 구조에서 부모 노드는 두 개의 자식 노드 중 우선 순위가 더 높은 자식과 비교하여 조건을 만족해야하기 때문입니다. 즉, 두 자식 중 하나가 아니라 더 우선순위가 높은 자식과 교환되어야 합니다. 이 과정에서 왼쪽 자식이 조건을 만족하더라도, 오른쪽 자식이 더 우선 순위가 높을 경우 오른쪽 자식과 교환해야 하므로 오른쪽 자식과도 비교가 필요합니다.

else if를 사용하지 않는 이유는, 왼쪽 자식과 비교 후 오른쪽 자식과 비교하는 것이 아니라, 왼쪽 자식이 조건을 만족하는지 확인한 후, 오른쪽 자식이 조건을 만족하는지도 독립적으로 확인해야 하기 때문입니다. 최종적으로 더 우선 순위가 높은 자식과 교환을 하기 위함입니다. 이 경우, 왼쪽 자식이 조건을 만족하더라도 오른쪽 자식이 더 우선 순위가 높을 수 있으므로, 두 자식 모두와의 비교가 필요하며, else if를 사용하면 이런 비교를 수행할 수 없습니다.

제공해 주신 코드는 힙의 조건을 만족시키기 위해 부모 노드와 자식 노드 간의 위치를 조정하는 로직을 담고 있으며, 이 과정에서 최대 힙이나 최소 힙의 조건에 따라 부모 노드가 두 자식 노드보다 크거나 작아야 하는 원칙에 따라 비교와 교환을 수행합니다.

Inflearn Community Q&A