힙 자료구조 구현(no swap version) (c/c++)

이 페이지는 swap을 하지 않는 힙 자료구조 구현에 대한 설명입니다.

응용 버전이기 때문에 전반적인 개념과 기본적인 구현법을 알고 싶으시면 아래 링크 참고해주시면 됩니다.

https://rightbellboy.tistory.com/342

힙 자료구조 개념 및 구현(w/ 배열) (C/C++)

 

위 링크에서 소개한 일반적인 힙 구현 코드는 아래와 같습니다. (min heap)

// swap (일반적인 형태)

const int LM = 7; // 1 base (6 + 1)
int h[LM], hn, c;

void swap(int c1, int c2) {
	int tmp = h[c1];
	h[c1] = h[c2];
	h[c2] = tmp;
}

void push(int v) {
	h[++hn] = v;
	for (c = hn; c > 1; c /= 2) {
		if (h[c] < h[c / 2]) swap(c, c / 2);
		else break;
	}
}

int pop() {
	if (hn <= 0) return -1; // empty

	swap(1, hn--);
	for (c = 2; c <= hn; c *= 2) {
		if (c + 1 <= hn && h[c + 1] < h[c]) c += 1;

		if (h[c] < h[c / 2]) swap(c, c / 2);
		else break;
	}
	return h[hn + 1];
}

 

push에서 새로 들어간 값 혹은 pop에서 최상단으로 올라온 값의 자리를 찾기 위해 swap을 반복하고 있습니다.

이는 곧 해당되는 값의 새로운 위치를 찾기 위해 기존 힙의 값들과 비교를 반복하는 형태라고 볼 수도 있습니다.

 

다시 말하면, 이 값을 직접 힙에 넣어서 swap을 하면서 다시 넣고 빼고 할 것이 아니라,

각 depth 별로 경쟁할 노드(push인 경우 부모, pop인 경우 자식)와 비교한 후 경쟁 노드만 위치를 옮겨주면 됩니다.

 

예를 들어 앞선 URL의 push(5)의 경우, 원래는 새로운 값인 5를 6번 index에 넣고 swap을 하게 되는데

no swap 버전은 v와 부모 노드(3번 index)를 비교한 뒤 v가 더 작을 경우 부모만 아래로 내려주면 됩니다.

(이해를 돕기 위해 3번 index 자리를 빈 칸으로 표시했지만 실제로는 6이 남아있습니다)

 

이러한 방식을 활용하면, 기존에 swap을 하면서 발생되는 세 번의 대입 연산을 단 한 번으로 줄일 수 있게 됩니다.

 

나머지 설명은 아래 코드로 대체하니 앞선 URL의 예시를 직접 따라가 보면서 습득하시길 바랍니다.

// no swap

const int LM = 7;
int h[LM], hn, c;

void push(int v) {
	for (c = ++hn; c > 1 && v < h[c >> 1]; c >>= 1) h[c] = h[c >> 1];
	h[c] = v;
}

int pop() {
	if (hn <= 0) return -1;

	int v = h[hn];
	h[hn--] = h[1];

	for (c = 2; c <= hn; c <<= 1) {
		c += (c < hn && h[c + 1] < h[c]);

		if (h[c] < v) h[c >> 1] = h[c];
		else break;
	}
	h[c >> 1] = v;
	return h[hn + 1];
}