[자료구조와 함께 배우는 알고리즘][정렬 알고리즘] - 힙 정렬(Heap Sort)

1. 힙 정렬 알아보기

• 힙 정렬은 힙의 특성을 이용해 정렬하는 알고리즘이다.
• 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다.
• 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 두 값의 대소 관계가 일정하면 힙이라고 할 수 있다.
• 이때 형제사이의 대소 관계는 일정하지 않는다.

 

• 최대 힙(Max heap)
  • 부모의 값이 자식의 값보다 항상 클 때
• 최소 힙(Min heap)
  • 부모의 값이 자식의 값보다 항상 작을 때

힙 정렬

 

 

💁‍♀️ 완전 이진 트리란? 

트리의 한 종류로 완전 이진 상태라는 특징이 있고, '완전'은 부모는 왼쪽 자식부터 추가하여 모양을 유지하라는 뜻으로 '이진'은 부모 노드가 가질 수 있는 자식 노드의 최대 개수는 2개라는 의미이다. 
즉, 왼쪽부터 추가하여 모양을 유지하며 부모 노드가 갖는 자식노드의 개수는 최대 2개를 가진 트리를 의미한다.

 

2. 루트를 삭제한 힙의 재구성

 

루트를 삭제하고 마지막 원소를 루트로 이동한다.

큰 값을 가진 자식과 위치를 교환한다.

 

---

루트를 삭제한 힙의 재구성 최종 모습

1. 루트를 꺼낸다.
2. 마지막 원소를 루트로 이동한다.
   • 가장 하단의 오른쪽에 위치한 원소를 선택하는 이유는? 왼쪽에서부터 완전이진트리를 넣어주기 때문에 가장 오른쪽 원소를 꺼내 올려야 함
3. 루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복한다.
   • 최소 힙일 때는 자신보다 값이 작은 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복한다. 
4. 자식의 값이 작거나 리프의 위치에 도달하면 종료한다.  

 

3. 힙 정렬 알고리즘 구현코드

# 힙정렬 알고리즘

def heap_sort(a):

    def down_heap(a,l,r):
        temp = a[l]

        parent = l
        while parent < (r + 1) // 2:
            cl = parent * 2 + 1
            cr = cl + 1
            child = cr if cr < r and a[cr] > a[cl] else cl
            if temp >= a[child]:
                break
            a[parent] = a[child]
            parent = child
        a[parent] = temp

    n = len(a)

    # a[i] ~ a[n-1]을 힙으로 만들기
    for i in range((n-1)//2,-1,-1):
        down_heap(a,i,n-1)

    # 최댓값인 a[0]과 마지막 원소를 교환
    for i in range(n-1,0,-1):
        a[0],a[i] = a[i], a[0]
        down_heap(a,0,i-1)
        

print("힙 정렬을 수행합니다.")
num = int(input("원소 수를 입력하세요:"))
x = [None] * num
for i in range(num):
    x[i] =int(input(f"x[{i}]: "))
heap_sort(x)

print("오름차순으로 정렬했습니다.")
for i in range(num):
    print(f"x[{i}] = {x[i]}")

 

4. heapq 모듈을 사용하는 힙 정렬

# heapq 모듈을 사용해서 힙 정렬

import heapq

def heap_sort(a):
    heap = []
    for i in a:
        heapq.heappush(heap,i)
    for i in range(len(a)):
        a[i] = heapq.heappop(heap)

        
print("힙 정렬을 수행합니다.")
num = int(input("원소 수를 입력하세요:"))
x = [None] * num
for i in range(num):
    x[i] =int(input(f"x[{i}]: "))
heap_sort(x)

print("오름차순으로 정렬했습니다.")
for i in range(num):
    print(f"x[{i}] = {x[i]}")

 

5. 힙 정렬의 시간 복잡도

힙정렬

O(n log n)

 

 

👽 heap은 최대값 최소값을 찾아주기 때문에  다익스트라 알고리즘에서 사용된다.