[자료구조] 힙(heap) 자료구조

 

힙은 우선순위 큐를 위하여 만들어진 자료구조이다. 힙에 대해 알아보기 전에, 우선순위 큐의 정의와 특징에 대해서 간략하게 정리해봤다. 

• 우선순위의 개념을 큐에 도입한 자료구조
• 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나감
• 시뮬레이션 시스템, 네트워크 트래픽 제어, OS에서 작업의 스케쥴링 등에 사용됨
• 배열, 연결 리스트, 힙으로 구현 가능하지만 힙을 이용하는 것이 가장 효율적

우선 순위 큐를 구현하는 방법	삽입 시간 복잡도	삭제 시간 복잡도
순서 없는 배열	O(1)	O(N)
순서 없는 연결 리스트	O(1)	O(N)
정렬된 배열	O(N)	O(1)
정렬된 연결 리스트	O(N)	O(1)
힙(heap)	O(logN)	O(logN)

 

 

힙(heap) 자료구조

💡 힙(heap)이란?

• 완전 이진 트리의 일종인 자료구조
  - 완전 이진 트리: 마지막을 제외한 모든 노드의 자식들이 꽉 채워진 이진 트리
• 우선순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값/최솟값을 빠르게 찾아내도록 만들어짐
• 최대 힙(max heap): (부모 노드의 키 값 >= 자식 노드의 키 값)을 만족하는 완전 이진 트리
• 최소 힙(min heap): (부모 노드의 키 값 <= 자식 노드의 키 값)을 만족하는 완전 이진 트리
• 느슨한 정렬 상태(반정렬 상태) 유지
• 이진 탐색 트리와 달리 중복 값 허용

 

 

💡 배열로 힙 구현하기

힙은 완전 이진 트리이기 때문에 빈 공간이 없어 배열로 구현하기에 용이하다. 구현을 쉽게 하기 위해 배열의 인덱스를 1부터 사용하면, 루트 노드를 1번으로 저장하게 된다. 이후 다른 노드들을 다음 그림과 같은 순서로 저장한다. 

 

 

💡 힙 재구조화(heapify)

힙에서 원소의 삽입이나 삭제가 일어나면 최대 힙의 조건이 깨질 수 있다. 이 경우 다시 최대 힙의 조건을 만족하도록 노드의 위치를 바꾸는 것을 재구조화(heapify)라고 한다. 

 

삽입과 삭제의 경우 연산 자체는 O(1)의 시간 복잡도로 작동하지만, heapify의 과정이 O(logN)이기 때문에 최종적으로 O(logN)의 시간 복잡도를 가지게 된다. 

 

<최대 힙 삽입 과정>

원소를 가장 말단 노드에 삽입한 다음, 가장 말단 노드부터 부모 노드와 값을 비교하면서 최대 힙 조건을 만족하는지 확인한다. 

 

 

 

최악의 경우 가장 말단에 삽입한 원소가 루트 노드까지 올라가게 되고, 이때의 비교 횟수는 트리의 높이만큼이다. 따라서 삽입의 경우 heapify의 시간 복잡도는 O(logN)이 된다. 

 

 

<최대 힙 삭제 과정>

가장 큰 원소인 루트 노드를 삭제하고 나면, 가장 말단의 원소를 루트로 이동시킨다. 이후 루트 노드부터 자식 노드와 비교하여 최대 힙 조건을 만족하는지 확인한다. 

 

삽입 과정과 유사하게, 최악의 경우 루트 노드에서 말단 노드까지 내려오게 되므로 비교 횟수는 트리의 높이만큼이다. 따라서 삭제 과정에서 heapify의 시간 복잡도는 O(logN)이 된다. 

 

 

💡 힙 만들기(build heap)

build heap은 힙이 아닌 배열을 힙으로 만드는 과정이다. 이때 heapify를 N번 진행하게 되므로 시간 복잡도는 O(NlogN)이다. 

 

<build heap 과정>

가장 말단의 오른쪽에 있는 노드의 부모 노드부터 위에서 아래로 heapify를 진행한다. 

 

 

 

💡 힙 정렬(heap sort)

힙 정렬은 추가적인 배열을 사용하지 않고 시간 복잡도 O(NlogN)에 수행 가능하다. 

• 내림차순 정렬 -> 최대 힙 사용
• 오름차순 정렬 -> 최소 힙 사용

힙 정렬은 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때 가장 유용하다. 만약 10개 원소 중에서 가장 큰 값 3개만 알고 싶다면, 최대 힙을 구성한 다음 가장 큰 값(루트 노드)을 3번 삭제하며 값을 확인하면 된다. 

 

<힙 정렬 과정>

1. 정렬할 N개의 원소로 최대 힙 구성
2. 최대 힙의 루트 노드(가장 큰 원소)와 마지막 원소 위치 교환
3. 새 루트 노드에 대해 최대 힙 구성
4. 원소 개수만큼 2와 3을 반복 수행

과정 1은 앞에서 살펴본 build heap 과정으로 O(NlogN)의 시간 복잡도를 가진다. 

과정 2와 3은 최대 힙에서 원소를 하나 삭제한 다음 heapify를 진행하는 것과 같으므로 O(logN)이 걸린다. 이 과정이 원소의 개수만큼 반복되므로 결국 O(NlogN)의 시간 복잡도를 가진다. 

따라서 힙 정렬의 O(NlogN) + O(NlogN) = O(NlogN)의 시간 복잡도를 가진다. 

 

 

 

Reference

• https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
• https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/
• https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap