힙 자료구조 개념 설명 및 예시 코드 (1 base) (C/C++)

1. 힙 자료구조 개념 설명

힙(Heap)은 우선순위 큐(Priority Queue) 구현을 위해 사용하는 자료구조입니다.
실제 제가 준비 중인 사내 알고리즘 시험에서도 가장 자주 사용되고 있습니다.
 
힙과 우선순위 큐를 이해하기 전에 큐 자료구조에 대해 이해를 하면 좋습니다.
큐에 대한 소개는 아래 링크 참고 바랍니다.
https://rightbellboy.tistory.com/343

큐 자료구조 개념 설명 및 예시 코드 (C/C++)

 
우선 순위 큐는 일반적인 큐와는 다르게 데이터를 뺄 때, 즉 dequeue시
자료 구조 내에서 우선 순위가 가장 높은 데이터가 나오게 됩니다.
 
이러한 형태로 우선 순위대로 데이터를 뽑을 수 있는 자료구조를 우선 순위 큐라고 하고,
이러한 우선 순위 큐를 완전 이진 트리 형태로 구현하면 '힙'이라고 표현합니다.
 
 
통상적으로 우선 순위는 데이터 값의 최소값 혹은 최대값으로 정하는데
그 특성에 따라 min heap, 혹은 max heap이라고 불리고 있습니다.
 
max heap은 큰 값이 높은 우선 순위를 갖는 형태이므로
pop을 할 경우 해당 heap 내에서 가장 큰 값이 나오게 됩니다.
(heap에서의 deque는 pop, enque는 push라고 칭합니다)
 
앞서 언급했듯이 힙은 완전 이진 트리 구조 형태로 구현됩니다.
따라서 최대값을 꺼내고 힙을 재배열할 때 최악의 경우 O(n)이 아닌 O(logn)의 시간복잡도를 갖게 됩니다.
(또한 데이터를 넣을 때도 O(logn)의 시간복잡도를 갖게 됩니다)
 
 
이러한 특성이 있기 때문에 자료구조에서 데이터가 빈번하게 들어오고 나가지만,
매번 가장 큰 값이나 가장 작은 값을 찾는 경우라면 힙을 사용하면 유용합니다.
만약 위 같은 상황에서 힙이 아닌 정렬을 사용하게 된다면 오히려 시간 비용이 훨씬 커집니다.
(반대로 데이터를 빼는 경우가 적은 상황이라면 아무데나(통상 맨 끝) 저장해두고
필요할 때 한 번 씩 정렬해서 사용하는 형태로 쓰는 것이 유리합니다)
 
 

2. 힙 자료구조 구현 방식

heap에 대한 개념 설명은 마치고 1차원 배열을 사용하여 구현하는 방법을 설명해보겠습니다.
(max heap으로 추후 작성 예정)
 
 

3. 힙 자료구조 구현 예시 코드

#include <cstdio>

struct _heap {
	int h[7], hn, c;

	void init() {
		hn = 0;
	}

	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() {
		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];
	}

	bool isEmpty() {
		return hn == 0;
	}
} HEAP;

int main() {
	HEAP.init();
	HEAP.push(3);
	HEAP.push(1);
	HEAP.push(7);
	HEAP.push(5);
	HEAP.push(4);
	HEAP.push(9);
	printf("heap is empty ? %s\n", HEAP.isEmpty() ? "true" : "false");
	printf("%d has been popped\n", HEAP.pop());
	printf("%d has been popped\n", HEAP.pop());
	printf("%d has been popped\n", HEAP.pop());
	printf("%d has been popped\n", HEAP.pop());
	printf("%d has been popped\n", HEAP.pop());
	printf("heap is empty ? %s\n", HEAP.isEmpty() ? "true" : "false");
	return 0;
}