개념

  • 데이터에서 최소값과 최대값을 빠르고 쉽게 찾기 위한

    완전이진트리

    형태의 자료구조

    • 완전이진트리: 마지막 레벨을 제외한 모든 레벨이 채워지고 마지막 레벨만 좌 → 우 구조

  • 모든 노드의 데이터는 부모노드는 자식 노드의 값보다 크거나 같다


힙 정렬

  1. root노드를 맨 마지막 인덱스 노드와 swap
  2. 맨 마지막 인덱스 노드는 없는 노드 취급하고 root 노드에서 heapify 작업
  3. 다시 root노드를 맨 마지막 인덱스 노드와 swap (2번에서 작업한 노드 제외)
  4. 반복

힙 정렬과 힙의 시간복잡도

힙의 시간 복잡도

힙의 높이는 O(log(n)) → 왼쪽, 오른쪽 자식은 (root * 2), (root * 2 + 1)이기에 log(n)번씩 건너서 확인하기 때문이고 이것을 전체 길이 n번만큼 반복하기에 힙의 시간 복잡도는 O(nlog(n))

힙정렬 시간 복잡도

  1. 리스트를 힙으로 생성
    1. nlog(n) → 한번의 heapify는 log(n) + 노드 전체 수가 n
  2. 루트 노드와 마지막 노드의 위치 변경 (변경 후 변경된 루트 노드는 없는 취급)
    1. n(1) → 없는거나 다름 없음
  3. 새로운 루트 노드가 힙 속성을 지킬 수 있게 heapify
    1. log(n) → 2와 3 합치면 log(n)
  4. 힙에 남아 있는 노드가 없도록 위에 2~3 반복
    1. nlog(n) → 1번의 행위를 다시 하는 것과 같음 (노드 전체)

정리하면 1번과 4번을 합쳤을때 2nlog(n) → O(nlog(n))

힙 정렬 은 O(nlog(n)) 의 시간복잡도를 가진다.


예제 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def swap(tree, index_1, index_2):
    temp = tree[index_1]
    tree[index_1] = tree[index_2]
    tree[index_2] = temp

def heapify(tree, root_index, tree_size):
    """heapify 함수"""

    # 왼쪽, 오른쪽 자식 노드의 인덱스
    left_child_index = 2 * root_index
    right_child_index = 2 * root_index + 1

    largest = root_index  # 부모 노드의 값이 가장 크다고 가정

    # 왼쪽 자식과 비교
    if 0 < left_child_index < tree_size and tree[largest] < tree[left_child_index]:
        largest = left_child_index

    # 오른쪽 자식과 비교
    if 0 < right_child_index < tree_size and tree[largest] < tree[right_child_index]:
        largest = right_child_index

    if largest != root_index:
        swap(tree, root_index, largest)
        heapify(tree, largest, tree_size)

def heapsort(tree):
    """ 힙 정렬 """
    tree_size = len(tree)
    for index in range(tree_size - 1, 0, -1):
        heapify(tree, index, tree_size)
    for i in range(tree_size - 1, 0, -1):
        swap(tree, 1, i)
        heapify(tree, 1, i)

data_to_sort = [None, 6, 1, 4, 7, 10, 3, 8, 5, 1, 5, 7, 4, 2, 1]
heapsort(data_to_sort)
print(data_to_sort)

https://user-images.githubusercontent.com/48043799/145683348-e7c02cbb-6aa8-4d04-b139-d84b65f9ab32.png