4주차

이진힙 : 완전이진트리 + 부모의 우선순위가 자식의 우선순위보다 높음

최대힙 : 내림차순, 최소힙 : 오름차순

 

힙 정렬

책에 나온 코드가 좀 복잡해서 gpt 돌린 코드로 이해해보자

def heapify(arr, n, i):
    largest = i
    left = 2*i
    right = 2*i+1
    if left <= n and arr[left] > arr[largest]:
        largest = left
    if right <= n and arr[right] > arr[largest]:
        largest = right

    if largest != i :
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr,n,largest)


def heap_sort(arr):
    n = len(arr)
    #처음에 최소 힙 만들어주기
    for i in range (n // 2, 0, -1):
        heapify(arr,n-1,i)

    #맨 앞의 값을 맨 뒤로 보내고 인덱스를 하나 줄여서 다시 힙히파이
    for i in range (n-1, 0, -1):
        arr[1], arr[i] = arr[i], arr[1]
        heapify(arr,i-1,1)


arr = list(map(int, input().split()))
arr = [0] + arr
print(arr)

heap_sort(arr)
print("힙 정렬 결과:", arr[1:])

먼저 힙소트를 호출하면 정렬할 배열 전체의 길이를 받아서 이진 트리의 높이(n//2) 만큼 루프를 돌면서

heapify로 이진 트리의 맨 밑에부터 부모와 좌우 자식의 크기를 비교해 스왑이 일어났으면 재귀적으로 heapify를 호출하며

초기 힙을 구성하고 맨 마지막 노드와 부모 노드를 스왑하고 스왑해서 맨 끝으로 보낸 노드 이외의 노드에 대해서 heapify하면서 정렬한다 

 

컴알 실습 문제