자료구조 / 힙(Heap)

자료구조 힙(Heap)은 최대값이나 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리이다.

힙에는 최상위 루트에 최대값이 들어가는 최대힙, 최상위 루트에 최소값이 들어가는 최소힙이 있으며, 공통적으로 부모노드와 자식노드의 대소관계가 성립하는 특성을 가진다.

 

 

최소힙과 최대힙 중 하나를 알면 다른 하나를 이해하는 것은 어렵지 않기 때문에, 최소힙에 노드를 추가하고 삭제하는 방법을 알아보자.

 

1. 최소힙에 노드 추가하기

마지막 노드에 추가할 값을 넣어준다. 그 후 부모노드와 자식노드의 대소관계가 성립할때까지 자리를 바꿔준다.

O(logN)의 시간 복잡도를 가진다.

int heap[16]; int hn; // hn : 5

- heap[0] :

- heap[1] : 2

- heap[2] : 4

- heap[3] : 3

- heap[4] : 5

- heap[5] : 6

 

heap[++hn] = 1;

for (int i = hn; i > 1; i /= 2)

{ 

    if (heap[i / 2] <= heap[i]) break;

    부모 노드인 heap[i / 2]와 자식 노드인 heap[i]를 스위치

}

void push(int* heap, int& hn, int x)
{
	int cur;
	heap[++hn] = x;
    
	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2] <= heap[i]) break;

		cur = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = cur;
	}
}

 

2. 최소힙에서 노드 꺼내오기

루트 노드에 있는 최소값이므로, 원하는 값을 얻어오기는 쉽다. 그러나 그 후에도 힙의 특성을 만족하도록 재 정비를 해주어야 한다.

마지막에 있는 값을 루트 노드로 올려서 부모노드와 자식노드의 대소관계가 성립할때까지 자리를 바꿔준다.

이또한 O(logN)의 시간 복잡도를 가진다.

int heap[16]; int hn; // hn : 6

- heap[0] :

- heap[1] : 1

- heap[2] : 4

- heap[3] : 2

- heap[4] : 5

- heap[5] : 6

- heap[6] : 3

 

minNode = heap[1];

heap[1] = heap[hn--];

for (int i = 1; i * 2 <= hn; ) { 

    if (heap[i] <= heap[i * 2] && heap[i] <= heap[i * 2 + 1]) break;

    if (heap[i * 2] <= heap[i * 2 + 1])

        부모 노드인 heap[i]와 자식 노드인 heap[i * 2]를 스위치

    else

        부모 노드인 heap[i]와 자식 노드인 heap[i * 2 + 1]을 스위치

int pop(int* heap, int& hn)
{
	int cur, minNode;

	minNode = heap[1];
	heap[1] = heap[hn--];

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i] < heap[i * 2] && heap[i] < heap[i * 2 + 1]) break;
		
  		if (heap[i * 2] < heap[i * 2 + 1])
		{
			cur = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = cur;
			i = i * 2;
		}
		else
		{
			cur = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = cur;
			i = i * 2 + 1;
		}
	}
	return minNode;
}

 

 

3. 우선순위 큐

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

우선순위 큐를 구현하기 위한 방법으로는 먼저 리스트를 사용하여 차례대로 값을 넣어둔 다음(삽입 시간 O(1)), 꺼낼때 우선순위가 높은 것을 찾아서 꺼내는 방법이 있다(삭제 시간 O(N)). 두번째로는 위에서 설명한 힙을 사용하는 방법이 있는데, 삽입 삭제 모두 O(logN)이 소요된다.

 

C++의 priority_queue를 이용하는 관련 문제는 아래와 같다.

 

https://guris-devlog.tistory.com/entry/프로그래머스-더-맵게

프로그래머스 / 더 맵게

 

4. 힙 정렬

힙에 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내면 정렬이 수행된다. 이 경우 시간 복잡도는 삽입 O(logN) * N번 + 삭제 O(logN) * N번으로, 총 O(NlogN)의 시간이 소요된다.