[MIT] 파이썬을 이용한 알고리즘의 이해 - 힙 & 힙 정렬

 

 

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

 

✔  우선순위 큐

 요소들 집합 S를 구현하는 자료구조입니다. 각 요소들은 key와 관련이 있고 다음 작업들을 지원합니다.

• insert(S, x) : 요소 x를 집합 S에 삽입
• max(S) : 최대 key인 S의 요소를 반환
• extract_max(S) : 최대 key인 S의 요소를 반환하고 집합 S에서 x 제거
• increase_key(S, x, k) : 요소 x의 key를 새로운 값 k로 증가(k가 현재 값만큼 크다고 가정)

 

 

 

✔  힙

•  우선순위 큐의 구현 가능
•  완전 이진 트리로 시각화된 배열
•  최대 힙 특성은 노드의 key가 자식 값들의 key보다 크거나 같음(최소 힙도 마찬가지로 동일하게 정의)

 

⁉️ 트리로서의 힙

트리의 루트	배열의 첫 요소, i=1
parent(i) = i/2	노드의 부모의 인덱스를 반환
left(i) = 2i	노드의 왼쪽 자식의 인덱스를 반환
right(i) = 2i + 1	노드의 오른쪽 자식의 인덱스를 반환

⭐ 포인터가 필요 없습니다. 이진 힙의 높이는 O(lg n)입니다.

 

⁉️ 힙에서의 연산

• build_max_heap : 정렬되지 않은 임의의 배열로부터 최대 힙을 만드는 메서드입니다.
• max_heapify       : 그 루트의 서브 트리에서 힙 특성을 위반한 걸 한 가지 고칩니다.
• insert, extract_max, heapsort 등

 

⁉️ 최대 힙화

• left(i)와 right(i) 서브 트리들이 최대 힙이라고 가정
• 만약 요소 A[i]가 최대 힙 특성을 위반한다면, 요소 트리 A[i]를 아래로 흘러 내려가도록 하면서 위반을 수정합니다. 인덱스 i의 서브 트리들을 최대-힙으로 만듭니다.

최대 힙화 예시

 

Build_Max_Heap(A)

Build_Max_Heap(A):
    for i in range(n/2, 1, -1):
        Max_Heapify(A, i)

  간단한 분석을 통하면 시간 복잡도는 O(n log n)입니다. 하지만 단말 노드보다 1단계 위에 있는 노드들은 Max_Heapify하는 데 O(1) 시간이 걸립니다. 일반적으로 단말 노드보다 1 단계 위에 있는 노드들은 O(1) 시간이 걸립니다. 1단계에서 n/4 노드들을 가지고, 2단계에서 n/8을 가지고, 한 개의 루트 노드만 남을 때까지 계속 이어집니다. 그렇기 때문에 마지막은 단말 노드로부터 log n 단계입니다. 이 단계들에서 걸린 시간들을 모두 더하면 아래와 같은 식이 됩니다.

그리고 위의 n/4 = 2^k라고 가정하면 다음과 같이 간단하게 바꿀 수 있습니다.(괄호 안의 각 항은 상수로 한정됩니다.)

👀 n/2부터 시작하는 이유 : 요소 A[n/2+1 ... n]들이 트리의 모든 단말 노드들이기 때문입니다.

⏱ 시간 복잡도 : O(n), Θ(n)

 

 

 

 

✔  힙 정렬

1. 정렬되지 않은 배열에서 최대 힙을 만듭니다.
2. 최대 요소 A[1]을 찾습니다.
3. 요소 A[n]와 A[1]을 스왑합니다. → 이제 최대 요소는 배열의 끝에 위치합니다.
4. 힙에서 노드 n을 제거합니다.(힙 크기 변수를 줄이는 방법을 통해서 진행합니다.) 
5. max_heapify로 최애 힙 특성을 수정합니다.
6. 힙이 비어있지 않다면 2단계로 돌아갑니다.

 n 번 반복 후 힙이 비게 된다. 각 반복은 스왑과 max_heapify 작업을 포함한다.

⏱ 전체 실행 시간 : O(n log n)