[자료구조] 힙 정렬
힙 정렬이란?
최대 힙의 루트가 전체 중 최댓값이라는 사실을 이용해 정렬하는 것. 최대 힙에서 루트를 반복적으로 제거해 나가며 정렬 리스트로 이동시키고, 남은 원소들을 가지고 최대 힙을 재구성한다. 이 과정을 반복하여 정렬을 수행한다. 최소 힙을 이용한 오름차순 정렬 역시 방식은 동일하다.
단, 파이썬의 heapq의 경우 최소 힙만을 제공한다. 따라서 파이썬에서 최대 힙을 사용하고자 하는 경우 원소의 부호를 바꾸어 최소 힙에 넣은 뒤, 루트를 제거할 때 다시 부호를 바꿔 주어 오름차순으로 정렬하는 방식을 이용한다.
힙 정렬의 시간 복잡도
최대 힙의 재구성 시간인 O(log₂n)과 반복 횟수(=원소 개수) n을 곱한 O(nlog₂n)이다.
힙 정렬 과정
- 원소를 완전 이진 트리에 저장해, 최대 힙으로 구성한다.
- 최대 힙의 루트를 마지막 원소와 교환하고, 이후의 정렬 과정에서 제외한다.
- 남은 원소를 가지고 최대 힙으로 재구성한다.
- 2번 과정을 반복한다.
- 정렬한 원소가 1개가 남았다면, 정렬을 종료한다.
이때, 최대 힙을 (재)구성하는 과정은 다시 아래와 같다.
- 노드 i의 자식 노드 2i, 2i + 1 중 큰 값을 선택하여 비교한다.
- 노드 i가 자식 노드보다 크다면, 알고리즘을 종료한다.
- 자식 노드가 노드 i보다 크다면 두 원소를 교환하고, 하위 레벨에서 비교 과정을 반복한다.
- 하위 레벨의 노드가 존재하지 않으면 알고리즘을 종료한다.
힙 정렬 파이썬 코드
정렬한 원소들은 num 리스트에 저장되어 있으며, 리스트에서 인덱스 [0]은 사용하지 않는다. 최대 힙이 재조정될 때마다, 루트가 이동하면서 리스트의 오른쪽(최대 힙의 마지막 원소 자리)부터 채워지는 것을 알 수 있다.
class HeapSort:
def __init__(self, num):
self.num = num
self.size = len(num)
print("Heap Sort", self.num)
def __str__(self):
for i in range (self.size):
print("%2d " % self.num[i])
# 루트와 마지막 원소를 교환하는 코드
def swap(self, a, b):
temp = self.num[a]
self.num[a] = self.num[b]
self.num[b] = temp
# 최대 힙을 (재)구성하는 코드
def makeheap(self, root, n):
temp = self.num[root]
child = 2 * root # 루트의 왼쪽 자식 노드
while child <= n:
# child가 자식을 가지고 있고, child보다 child + 1 값이 더 크다면 비교 대상을 오른쪽 자식 노드로 변경
if child < n \
and self.num[child] < self.num[child + 1]:
child += 1
# 부모가 자식보다 크다면 재구성 종료
if temp > self.num[child]:
break
# 자식이 부모보다 크다면 하위 레벨에서 다시 비교 시작
else:
self.num[child // 2] = self.num[child]
self.num[child // 2] = temp
def sort(self):
n = self.size - 1
# 자식 노드를 갖는 노드(n // 2)부터 루트까지 최대 힙 조건에 맞도록 구성
for i in range (n // 2, 0, -1):
self.makeheap(i, n) # 초기 최대 힙 구성
print(self.num)
for i in range (n - 1, 0, -1):
self.swap(i, i + 1) # 루트와 마지막 원소 교환
self.makeheap(1, i) # 재구성할 노드와 노드의 수
print(self.num)
num = [0, 24, 7, 80, 3, 64, 15, 50, 60, 20]
s = HeapSort(num) # 인스턴스 생성
s.sort() # 힙 정렬 수행
참고 도서: 파이썬으로 배우는 자료구조 프로그래밍, 유석종 저