[파이썬 자료구조] 힙정렬(heap sort)

[파이썬 자료구조] Binary Heap

---

힙정렬

힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다....라고 위키에 써져있음

간단히 살펴보자

1단계.  5가 삽입된 경우임. 트리의 맨 아래에서 왼쪽에다가 붙혀줌

2단계. 위를 쳐다보니 40이 있다. 5가 더 작으니까 40과 교환한다.

3단계. 위를 쳐다보니 이제 20이 있다. 5가 더작으니까 교환한다.

4단계. 또 위를 쳐다보니 15가 있다. 5가 더작으니까 교환한다.

힙구현은 파이썬 기본모듈인 heapq를 import하면 쉽게 사용 가능

heap을 직접 구현하라해도 쉽게 할 수 있을듯?

import heapq
 
def heap_sort(nums):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
    sorted_nums = []
    while heap:
        sorted_nums.append(heapq.heappop(heap))
    return sorted_nums
 
 
if __name__ == "__main__":
    print(heap_sort([4, 1, 7, 3, 8, 5]))

그래서 힙정렬의 장점이 무어냐면 정렬 중에서 수행시간이 최적이라는 것이다.

n개를 정렬하는데 걸리는시간이 O(n*log(n))임