힙 트리

최근 수정 시각: 2026-02-17 12:25:09

분류

자료구조

[ 펼치기 · 접기 ]

이론
기본 대상	수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론	재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 · 디지털 물리학
오토마타 이론	FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론	점근 표기법 · 튜링 기계^{고전, 양자, 비결정론적, 병렬 임의접근 기계} · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법, 분할 정복 알고리즘)
정보이론	정보 엔트로피 · 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어론	프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타프로그래밍 · 람다 대수 · 타입 이론 · 프로그래밍 언어 의미론 · 어휘 분석 · 파싱 · 구문 트리(완전 구문 트리 · 추상 구문 트리) · 컴파일러 이론
주요 알고리즘 및 자료구조
기초	정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현	배열^벡터 · 리스트^{연결 리스트} · 셋(set) · 트리^{이진 트리(레드-블랙 트리, 힙), B-트리, 피보나치 힙} · 큐 · 스택
수학적 최적화	조합 최적화	외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
	볼록 최적화	내부점 방법 · 경사하강법
	선형계획법	심플렉스법
계산 수론 및 암호학	밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 · 난수생성
	대칭키 암호화 방식	블록 암호 알고리즘(파이스텔 네트워크 · DES · AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
	공개키 암호화 방식	공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학	볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^{Fortune의 line-sweeping 알고리즘} · 범위 탐색^{vp-tree, R-tree} · k-NN
그래프 이론	탐색^{BFS, DFS, 다익스트라 알고리즘, A* 알고리즘} · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제^{대각선 논법} · 암달의 법칙 · P-NP 문제^미해결 · 콜라츠 추측^미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학

1. 개요2. 정의3. 데이터 처리

3.1. 데이터 삽입3.2. 데이터 삭제

4. 배열 표현

4.1. 빌드

5. 응용 분야6. 코드

6.1. C++

1. 개요[편집]

heap tree
여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리. 짧게 힙(heap)이라고 줄여서 부르기도 한다.

영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 힙은 항상 완전 이진 트리 [1]의 형태를 띠어야 하고, 부모의 값은 항상 자식(들)의 값보다 크거나(최대 힙[max heap]), 작아야(최소 힙[min heap])하는 규칙이 있다. (그러므로 사진은 최소 힙[min heap]이다.) 따라서 루트 노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장되어 있기 때문에, 최댓값(혹은 최솟값)을

O(1)

안에 찾을 수 있다.

아래는 '최댓값 찾기'에 관련된 행위들과, 그 행위들이 걸리는 시간복잡도를 나열한 것이다.

	생성 & 읽기 : 무작위 수열에서부터	수정 : 수 추가하기	삭제 : 다음 최댓값 찾기
정렬하기	$O(NlogN)$	$O(logN)$	$O(1)$
힙 트리	$O(N)$	$O(logN)$	$O(logN)$
그냥 순회하며 찾기	$O(N)$	$O(1)$	~~$O(N)$~~

단순히 최댓/최솟값을 단 한 번만 찾아야 한다면 그냥 전체를 한 번 쓱 보는 것만으로

O(N)

로 충분하다. 하지만 실제로는 자주 다익스트라 알고리즘처럼 "다음 최댓값도 알고 싶"을 것이다.
이 때 그냥 순회하며 찾기는 쓸 수 없게 된다. 그렇다고 매번 전체를 정렬하자니 정렬 자체에 드는 비용

O(NlogN)

이 너무 크다. 대신 힙은 다음 최댓값을 찾을 때

O(logN)

을 다소 감수하더라도 최초 힙 생성에 $O(N)$ 밖에 안 쓴다. 즉, "데이터가 뭉텅이로 들어와서 빠르게 구조를 잡아야 하고(

O(N)

), 전체를 정렬할 필요 없이 최댓값/최솟값만 반복적으로 꺼내면 되는" 상황에서 힙은 정렬에 비해 압도적인 효율성을 보여준다.

단순히 최댓값(최솟값)을

O(1)

안에 찾기 위해서라면 '항상 완전 이진 트리의 형태여야 한다'는 조건을 만족시킬 필요는 없다. [2] 완전 이진 트리를 사용하는 이유는 삽입/삭제의 속도 때문이다. 물론 '힙 트리'는 정의상 완전 이진 트리를 사용하는 트리다. 달리 다른 구조를 사용한다 해도 전혀 얻을 게 없는 최적의 구조이기 때문.

3. 데이터 처리[편집]

데이터의 삽입과 삭제는 모두

O(\log N)

이 소요된다.
heap은 완전 이진 트리의 구조를 가지고 있기 때문에 트리의 레벨이 늘어날수록 노드의 수는 두 배씩 증가한다.
그 말은 레벨이 i라고 가정했을 때 i레벨의 노드 수는

2^{i-1}

개이다. (단 i는 마지막 레벨은 아니다. 이는 완전 이진 트리의 특성 때문이다.)
그러므로 트리의 높이는 노드의 수를 통해서 알 수 있다.
트리의 높이는

log_2i+1

에서 소수점을 버린 값이다.
Heap에서 데이터의 삽입과 삭제는 이 높이와 관련이 있기 때문에 빅오 표기법에 의해

O(\log N)

이렇게 표현되는 것이다.

3.1. 데이터 삽입[편집]

가장 끝의 자리에 노드를 삽입한다.
그 노드와 부모 노드를 서로 비교한다.
규칙에 맞지 않는다면 부모와 교환하고, 교환되어 올라간 위치에서 과정을 반복한다.[3][4]
규칙에 맞는다면 과정을 끝낸다.

위와 같이 반복적으로 부모와 비교하며 노드를 위로 올리는 과정을 'sift up' 또는 'percolate up'이라 칭한다.

3.2. 데이터 삭제[편집]

최댓값 혹은 최솟값이 저장된 루트 노드를 제거할 수 있다.

루트 노드를 제거한다.
가장 마지막 노드 (L)를 루트 노드로 이동시킨다.[5]
노드 L을 자식 노드(들)와 비교한다. 규칙을 만족하면 끝내고, 그렇지 않으면 L을 자식과 교환한다. 최소(최대) 힙에서 과정을 구체적으로 나타내면 다음을 반복하는 것과 같다.
3.1. 자식들의 크기를 비교하여 더 작은(큰) 자식을 찾는다.
3.2. 더 작은(큰) 자식이 L보다 크거나(작거나) 같다면 과정을 끝낸다.
3.3. 더 작은(큰) 자식이 L보다 더 작다면(크다면) 교환한다.[6]

위와 같이 반복적으로 자식과 비교하며 노드를 아래로 내리는 과정을 'sift down' 또는 'percolate down'이라 칭한다.

한편, 유사한 방식으로 임의의 위치에 있는 노드 또한 제거할 수 있다.

노드를 제거한다. 마지막 노드였다면 과정을 끝낸다.
가장 마지막 노드 (L)를 빈 노드로 이동시킨다.
노드 L을 부모 노드와 비교한다. 규칙을 만족하면 반복을 끝내고, 그렇지 않으면 L을 부모와 교환한다. 최소(최대) 힙에서 과정을 구체적으로 나타내면 다음을 반복하는 것과 같다.
3.1. L이 부모보다 크거나(작거나) 같다면 반복을 끝낸다.
3.2. L이 부모보다 더 작다면(크다면) 교환한다.
노드 L을 자식 노드(들)와 비교한다. 규칙을 만족하면 끝내고, 그렇지 않으면 L을 자식과 교환한다. 최소(최대) 힙에서 과정을 구체적으로 나타내면 다음을 반복하는 것과 같다.
4.1. 자식들의 크기를 비교하여 더 작은(큰) 자식을 찾는다.
4.2. 더 작은(큰) 자식이 L보다 크거나(작거나) 같다면 과정을 끝낸다.
4.3. 더 작은(큰) 자식이 L보다 더 작다면(크다면) 교환한다.

다만, 임의의 값을 제거하기 위해 해당 값이 들어 있는 노드를 찾는 과정은 매우 비효율적이므로, 노드의 위치를 기록해놓는 자료 구조를 미리 구축해두어야 한다. 삽입과 루트 노드 제거의 시간복잡도가 증가하지 않도록 해당 자료 구조는 배열을 사용한다.

4. 배열 표현[편집]

이진 힙은 완전 이진 트리(complete binary tree)로서, 배열로 표현하기 매우 좋은 구조다. 높이 순서대로 순회하면 모든 노드를 배열에 낭비 없이 배치할 수 있기 때문이다. 그림처럼 완전 이진 트리는 배열에 빈틈없이 배치가 가능하며, 대개 트리의 배열 표현의 경우 계산을 편하게 하기 위해 인덱스는 1부터 사용한다.

해당 노드의 인덱스를 알면 깊이가 얼마인지, 부모와 자식 노드가 배열 어디에 위치하는지 바로 알아낼 수 있다. 깊이는 1, 2, 4, 8, ... 순으로 2배씩 증가하며, 인덱스는 1부터 시작했기 때문에 부모/자식 노드의 위치는 각각 부모

\lfloor\frac{i}{2}\rfloor

, 왼쪽 자식

2i

, 오른쪽 자식

2i+1

의 간단한 수식으로 계산할 수 있다. 이처럼 해당되는 배열의 인덱스를 금방 찾아낼 수 있다. 물론 꼭 완전 이진 형태가 아니어도 비어있는 위치는 얼마든지 널(null)로 표현할 수 있기 때문에, 사실상 모든 트리는 배열로 표현이 가능하다.

4.1. 빌드[편집]

역으로, 배열이 주어지면 이에 대응하는 완전 이진 트리가 존재하게 되는데, 당연하게도 힙의 규칙을 만족하지는 않을 확률이 높다. 이러한 트리를 규칙을 만족하도록 수정하는 과정을 '빌드 힙(build heap)' 또는 'heapify'로 부른다.

배열의 모든 원소를 대응되는 트리의 위치에 둔다.
자식을 가지는 가장 마지막 노드[7]에 대해 'sift down'을 수행한다.
인덱스를 하나씩 줄이며 'sift down'을 수행한다. 'sift down'하여 내려간 노드가 여전히 규칙을 만족하지 않는다면 내려간 노드의 규칙을 먼저 맞춘다.
루트 노드까지 과정이 완료되면 종료한다.

원소가 총

N

개라면, 자식을 한 단계 가지는

\frac{N}{4}

개의 노드에 대해서는 1회의 작업, 자식을 두 단계 가지는

\frac{N}{8}

개의 노드에 대해서는 2회의 작업, 자식을 세 단계 가지는

\frac{N}{16}

개의 노드에 대해서는 3회의 작업 등을 수행한다. 따라서 빌드에 소요되는 시간은

T(N) = O(1) \cdot \frac{N}{4} + O(2) \cdot \frac{N}{8} + O(3) \cdot \frac{N}{16} + \cdots = O(N)

이다.[8]
비어있는 힙에 데이터 삽입을

N

회 반복하는 방법도 생각할 수 있으나, 이 경우엔 부모를

\log N

단계 가지는

\frac{N}{2}

개의 노드에 대해서

\log N

회 작업, 부모를

\log N-1

단계 가지는

\frac{N}{4}

개의 노드에 대해서

\log N-1

회 작업 등을 하므로 빌드에 소요되는 시간이

T(N) = O(\log N) \cdot \frac{N}{2} + O(\log N - 1) \cdot \frac{N}{4} + \cdots = O(N\log N)

이다.

5. 응용 분야[편집]

힙의 형태를 보면 최대 힙의 경우 루트가 항상 최댓값이고, 최소 힙의 경우 루트가 항상 최솟값임을 알 수 있다.
이를 이용하여 우선순위 큐(priority queue)를 구현하거나, 힙 정렬(heap sort)을 만드는 등의 일을 할 수 있다.
또한 무손실 압축 알고리즘(?)인 허프만 코드도 힙의 구조를 기반으로 하고있다.

6. 코드[편집]

6.1. C++[편집]

최소 힙 기준으로 짜인 소스이다.

삽입

void creheap(int *arr2, int key, int input) {
  arr2[key] = input;
  while (key > 1) {
    if (arr2[key] < arr2[key / 2]) {
      swap(arr2[key], arr2[key / 2]);
      key /= 2;
    }
    else break;
  }
}

삭제
루트 노드 삭제 후 힙의 마지막 데이터를 가져온 상태를 가정한다.

void delheap(int *arr3, int key, int heap_size) {
  int tmp, nextkey;
  while (heap_size >= key * 2) {
    if (key * 2 + 1 > heap_size && arr3[key * 2] < arr3[key]) {
      swap(arr3[key * 2], arr3[key]);
      key = key * 2;
    }
    else if (key * 2 + 1 > heap_size) break;
    else {
      if (arr3[key * 2] < arr3[key * 2 + 1]) {
        tmp = arr3[key * 2];
        nextkey = key * 2;
      }
      else {
        tmp = arr3[key * 2 + 1];
        nextkey = key * 2 + 1;
      }
      if (tmp < arr3[key]) {
        swap(arr3[key], arr3[nextkey]);
        key=nextkey;
      }
      else break;
    }
  }
}

[1] 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리.[2] 극단적으로 말해서, 최댓값/최솟값을 항상 헤드에 두고, 나머지 데이터는 비교하든 말든 그냥 뒤에 쭉 이어 붙인 연결 리스트로도 최댓값/최솟값을 상수 시간 내에 찾을 수 있다.[3] 부모 노드는 삽입된 위치의 인덱스 번호에서 /2를 하면 쉽게 구할 수 있다.[4] 최소 힙을 예시로 든다면 형제 노드 > 부모 노드이고, 만약 부모 노드 > 삽입된 노드라면 교환을 수행해도 형제 노드 > 삽입된 노드이므로 규칙이 깨지지 않는다.[5] 이는 수정될 힙에서 중간에 빈 공간이 생기지 않게 하기 위함이다[6] 자식 중 더 작은(큰) 노드를 교환하여 올렸으므로 교환을 수행해도 규칙이 깨지지 않는다.[7] 전체 노드 개수를 2로 나누어 구할 수 있다.[8]

T(N)

에서

\frac{1}{2}T(N)

을 빼면 쉽게 보일 수 있다.

이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 및 삽화 제외)
기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.

나무위키는 백과사전이 아니며 검증되지 않았거나, 편향적이거나, 잘못된 서술이 있을 수 있습니다.
나무위키는 위키위키입니다. 여러분이 직접 문서를 고칠 수 있으며, 다른 사람의 의견을 원할 경우 직접 토론을 발제할 수 있습니다.