[힙 구조] 이진 힙

작성일 | In

힙이란?

힙은 최대값 혹은 최소값을 빠르게 찾아내는 것을 목적으로 고안된 트리를 기반(tree-based structure)으로 한 자료구조입니다.

힙은 다음 속성을 만족합니다.

  • A가 B의 부모노드이면, A의 키값과 B의 키값 사이에는 대소관계가 성립한다.

힙은 최대힙(MaxHeap)과 최소힙(MinHeap)이 있습니다. 최대힙에서는 부모노드의 키가 자식모드의 키보다 항상 크고, 최소힙에서는 그 반대의 상태를 항상 유지합니다.
키값의 대소관계는 오직 부모-자식 사이에서만 존재합니다.
이 조건을 통해 루트 노드는 최대 혹은 최소 값이라는 것이 보장됩니다.

이진 힙의 구현

이 글에서는 가장 대중적으로 쓰이는 이진 힙을 다룰 것입니다.
이진 힙은 이름에서 알 수 있듯이 이진 트리 형태를 유지합니다. 즉, 자식 노드 수는 최대 2개입니다.
추가로, 완전 이진 트리 상태를 유지합니다.

최대힙을 기준으로 설명하겠습니다.

먼저, 힙은 완전 이진 트리 상태를 유지하므로 일차원 배열을 이용해 구현하겠습니다.

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

template <typename T>
class heap{
	private:
		vector<T> arr;
	public:

};

부모 노드와 자식 노드를 구하는 메소드를 만들어봅시다.

1
2
3
int getPar(int idx){ return (idx-1)/2; }
int getLeft(int idx){ return 2*idx+1; }
int getRight(int idx){ return 2*idx+2; }

insert

힙의 삽입 연산은 4단계로 구성이 되어 있습니다.

  1. 힙의 가장 아래, 오른쪽에 삽입할 노드 추가
  2. 추가한 노드를 부모 노드와 비교
  3. 부모 노드가 더 작으면 swap, 그렇지 않으면 연산 종료
  4. 추가 노드가 루트 노드에 위치하게 되면 연산 종료, 그렇지 않으면 2번으로 복귀 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void insert(T data){
 if(arr.size() == 0){
     arr.push_back(data); return;
 }
 int now = arr.size();
 int par = getPar(now);
 arr.push_back(data);
 while(now > 0 && arr[now] > arr[par]){
     swap(arr[now], arr[par]);
     now = par; par = getPar(now);
 }
}

remove

최대힙의 최대값 제거 연산은 5단계로 이루어져 있습니다.

  1. 루트 노드의 키값을 따로 저장
  2. 가장 아래, 오른쪽에 있던 노드를 루트 노드로 이동
  3. 옮긴 노드를 양쪽 자식과 비교하여 자신보다 작은 자식과 swap, 그렇지 않으면 5번으로 이동
  4. 옮긴 노드의 자식이 없으면 5번으로 이동, 그렇지 않으면 3번으로 복귀
  5. 1번에서 저장한 값 반환 후 연산 종료 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    T remove(){
  T ret = arr[0];
  arr[0] = arr.back();
  int left = getLeft(0), right = getRight(0);
  int sel = 0, par = 0;
  while(1){
 if(left >= arr.size()) break;
 if(right >= arr.size()) sel = left;
 else{
   if(arr[left] > arr[right]) sel = right;
   else sel = left;
 }

 if(arr[sel] < arr[par]){
   swap(arr[sel], arr[par]);
   par = sel;
 }else break;

 left = getLeft(par);
 right = getRight(par);
  }
  return ret;
}

전체 코드

전체 코드는 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
template <typename T>
class heap{
	private:
		vector<T> arr;
		int getPar(int idx){ return (idx-1)/2; }
		int getLeft(int idx){ return 2*idx+1; }
		int getRight(int idx){ return 2*idx+2; }
	public:
		void insert(T data){
			if(arr.size() == 0){
				arr.push_back(data); return;
			}
			int now = arr.size();
			int par = getPar(now);
			arr.push_back(data);
			while(now > 0 && arr[now] > arr[par]){
				swap(arr[now], arr[par]);
				now = par; par = getPar(now);
			}
		}
		T remove(){
			T ret = arr[0];
			arr[0] = arr.back();
			int left = getLeft(0), right = getRight(0);
			int sel = 0, par = 0;
			while(1){
				if(left >= arr.size()) break;
				if(right >= arr.size()) sel = left;
				else{
					if(arr[left] > arr[right]) sel = right;
					else sel = left;
				}

				if(arr[sel] < arr[par]){
					swap(arr[sel], arr[par]);
					par = sel;
				}else break;

				left = getLeft(par);
				right = getRight(par);
			}
			return ret;
		}
};