[알고리즘] Heap sort (힙정렬)

Heap

 

• Binary Tree 일종이다. Priority Queue를 위하여 만들어진 데이터구조이다
• 간단하게 말해서 최대값과 최솟값을 효율적으로 추출할 수 있도록 하는 방법

 

Max heap 개념 (Min heap은 이와 반대)

1. max heap 삽입

• heap에 새로운 element가 들어오면, 새 노드를 heap의 마지막 노드에 이어서 삽입
• 새로운 노드를 부모 노드들과 교환을 통해서 힙을 정렬

다음의 일련의 과정을 거쳐서 새로운 노드가 8이 들어올 경우 바꿔주며 정렬을 시작한다

 

 

2. max heap 삭제

• 최대 힙에서 최대값은 루트 노드로 이를 삭제한다
• 삭제된 루트 노드에 마지막 노드를 가져온다
• 1번에서 나온 방법과 같이 heap을 구성한다

 

heap sort는 시간복잡도가 상당히 효율적인 편이다. 따라서 전체 자료중에서 최대, 최소값이 필요하다면 가장 널리쓰이는 자료구조이므로 무조건 알아두자

 

시간복잡도를 계산한다면 힙 트리의 전체 높이가  log₂n 이므로 하나의 요소를 힙에 넣을 시나 삭제될 시 다음과 같은 복잡도가 나오게 되고, 전체 element가 N개 이므로 O(Nlog₂n) 이 시간복잡도가 되겠다

 

 

 

Python 사용 (heapq module)

heapq 모듈은 python 내장 모듈로 따로 import를 통해 불러오자

from heapq import heappush, heappop, heapify

 

Heap에 원소를 추가 삭제하는 것은 heappush 와 heappop을 사용하면 된다

heap = []
heappush(heap,4)
heappush(heap,1)
heappush(heap,7)
heappush(heap,3)
print(heap)

>>>[1, 3, 7, 4]

heappop(heap)
>>> 1

print(heapq)
>>>[3,7,4]

 

만약 원소가 있는 일반 리스트를 힙으로 만들고 싶다면 heapify() 함수를 이용하자

heap = [4,1,7,3,2,6]
heapify(heap)
print(heap)

>>> [1, 2, 6, 4, 3, 7]

 

※ 여기서 heapify()는 인자로 넘긴 일반 리스트의 요소에 비례하여 O(n)의 복잡도를 가진다 (heap sort와 약간 다름)

 

 

reference : https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html