힙 정렬(heap sort)

📔 힙 정렬(heap sort) 이란

• 힙트리구조를 이용하여 정렬하는 알고리즘
  힙트리: 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리
• 힙정렬을 하기 위해서는 먼저 힙 구조를 가지도록 만들어야 한다.
  히피파이 알고리즘을 통해 힙구조로 만든다.
• 모든 정점에 대해서 히피파이를 수행하므로 n x logn 의 시간복잡도를 가진다.
  사실상 모든 정점이 아니라 절반의 정점만 해도 가능하다
  n/2 x logn => (n/2이 logn 보다 크다고 가정할 때) => 결국 O(n) 의 시간복잡도를 가진다.

 

📔 힙 정렬(heap sort) 구현

# (최대)힙 구조 만들기
def heapify():
    for i in range(1, N):
        c = i
        while c > 0:
            root = (c - 1) // 2
            if numbers[c] > numbers[root]:
                numbers[c], numbers[root] = numbers[root], numbers[c]
            c = root
    return


# 힙 정렬하기(오름차순)
def heap_sort():
    for i in range(N - 1, -1, -1):  # n
        # 맨 앞과 맨 뒤를 교환! ( 가장 큰 수를 뒤로 보낸다. 그리고 그 가장 큰 수는 FIX!!!! )
        numbers[0], numbers[i] = numbers[i], numbers[0]

        # 힙구조가 이상해졌으므로 다시 힙구조로 바꾼다.  # logn
        root, c = 0, 1
        while c < i:
            c = root * 2 + 1
            if c < i - 1 and numbers[c] < numbers[c + 1]:
                c += 1

            if c < i and numbers[c] > numbers[root]:
                numbers[c], numbers[root] = numbers[root], numbers[c]
            root = c
    return


numbers = [2, 7, 3, 4, 5, 6, 1]
N = len(numbers)
heapify()
print(numbers)
heap_sort()
print(numbers)

 

📔 힙 정렬(heap sort) 특징

• 장점
  • 추가적인 배열이 필요하지 않다.( in-palce algorithm, 병합정렬보다 효율적 )
  • 항상 nlogn을 보장
  • 이론상 퀵,병합 정렬보다 우위에 있다.
  • max 또는 min 값을 구할 때 시간 복잡도는 O(1)이다.
• 단점
  • 일반적으로 속도만 비교하자면 퀵이 평균적으로 더 빠르다. 그래서 잘 사용하지 않음.

 

📔 힙 정렬(heap sort) 참교자료