알고리즘 – 힙 (Heap)

• heap 이란?
  • 우선순위 큐 구현을 위한 자료구조로 최대, 최솟값을 찾기 용이
    • 완전 정렬이 아닌 반정렬 구조
  • 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리 구조
    • 큰 경우 – 최대 힙
    • 작은 경우 – 최소 힙
  • heap 에서의 부모 노드와 자식 노드의 관계
    • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
    • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
    • 부모 인덱스 = 자식 인덱스 // 2
  • 힙 정렬 알고리즘의 시간복잡도
    • 최악, 최선, 평균 – O(logN)
    • 참고 – 각 정렬 알고리즘의 시간복잡도

• 예제 – 최대 힙 정렬

# Python Code

def heapify(arr, idx, n):
    l_idx = idx * 2
    r_idx = idx * 2 + 1
    change_idx = idx
    if r_idx <= n and arr[change_idx] < arr[r_idx]:
        change_idx = r_idx
    if l_idx <= n and arr[change_idx] < arr[l_idx]:
        change_idx = l_idx
    
    if change_idx != idx:
        arr[change_idx], arr[idx] = arr[idx], arr[change_idx]
        heapify(arr, change_idx, n)

def heap_sort(arr):
    n = len(arr)
    arr = [0]+arr

    for idx in range(n, 0, -1):
        heapify(arr, idx, n)
    
    return arr

arr = [9,7,4,6,2,1,3,3,4,1]

arr.append(9)

print(heap_sort(arr))
# [0, 9, 9, 4, 6, 7, 1, 3, 3, 4, 1, 2]

• 과정 – 최대 힙

이후 부모 노드가 자식 노드보다 작지 않으므로 추가적인 교체는 없다.

최소 힙와 최대 힙은 큰 값과 작은 값에 대한 비교의 차이일 뿐이니 생략하겠습니다. 😁