[MIT 6.006 정리] Lec 04. 우선순위 큐, 힙, 힙 정렬

* 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D

 

------- * ------- * ------- * -------

 

 

* 우선순위 큐 (Priority Queue)

• 요소들의 집합(a set of elements) S 를 구현한 자료구조로서, 각 요소는 연관된 키(key) 를 가짐
• 수행 가능한 연산(operations)
  1. 삽입  insert(S, x) : 요소 x 를 집합 S 에 삽입함
  2. 최대값 (확인)  max(S) : 집합 S 에서 가장 큰 키(key) 값을 갖고 있는 요소를 리턴함
  3. 최대값 추출  extract_max(S) : 집합 S 에서 가장 큰 키 값을 갖고 있는 요소를 리턴한 뒤, 집합 S 에서 제거함
  4. 키 값 증가  increase_key(S, x, k) : 집합 S 의 요소 x 의 키를 새로운 값 k 까지 증가시킴

+ 추상 자료형  (Abastract Data Type, ADT)

 

* 힙 (Heap)

• 우선순위 큐 자료구조의 구현  (우선순위 큐 : 힙 = 추상자료형 : 구현?)
• • 모든 배열은 힙 구조로 표현(시각화) 가능
  • 임의의 크기를 갖는 배열을 가정하므로 포화 이진트리(full binary tree) 는 아닐 수 있음!
  • 완전 이진트리(complete binary tree) 형태로 시각화된(visualized) '배열(array)' 자료구조

 

• 트리로서의 힙(Heap as a Tree) 은 아래와 같이 정의할 수 있음
  • 루트 노드  root  =  배열의 첫번째 원소 (i = 1, when index i = 1, ... ,n)
  • 인덱스 i 인 원소의 부모 노드  parent(i)  =  i / 2
  • 인덱스 i 인 원소의 왼쪽 자식  left(i)  =  2i  &  오른쪽 자식  right(i)  =  2i + 1

 

* 최대 힙(Max Heap) / 최소 힙(Min Heap)

• '모든 노드의 키(key) 값이 그 자식 노드의 키 값보다 크거나 같다 / 작거나 같다는 특성' 을 갖는 힙 구조
• 단말 노드(leaves) 는 자식 노드가 없으므로 언제나 최대 / 최소 힙 특성을 만족하는 것으로 간주
• 힙을 수정하게 되어도 이러한 고유의 특성을 유지하고자 함 (자료구조의 불변성)
• 최대 / 최소 힙 특성을 갖지 않는 (그냥) 힙 구조의 자료도 물론 존재 가능!
• 힙 연산들(Heap operations)
  
  1. 최대 힙 구축 build_max_heap : 임의의 배열(an arbitrary & unordered array) A 로부터 최대 힙을 만드는 메소드.
  2. 최대 힙-화 max_heapify : 서브트리(sub-tree) 의 루트에서 힙 특성을 해치는 오류를 하나 수정하는 연산으로, build_max_heap 을 수행하기 위해 필요한 기본적인(fundamental) 연산

* 최대 힙-화 (max_heapify) in detail

• 최대 힙-화 연산은 완전히 임의의(arbitrary) 배열 A 을 입력으로 받는 것이 아니라, 최대 힙에서 약간 모자란 것(기본적으로 힙 구조이나 최대 힙 특성을 해치는 하나의 오류(a single violation) 가 서브트리에 존재하는...!) 을 받아 해당 오류를 수정하고 최대 힙을 리턴함

• 전제 조건: i 번째 노드의 왼쪽 / 오른쪽 서브트리가 이미 최대 힙 특성을 만족하는 상태라고 가정!
• 복잡도(Complexity): O(1) * log n = O(log n)
  1. 힙 구조는 기본적으로(by definition) '완전 이진트리' 임  -->  완전 이진트리 특성상, 트리의 높이가 'log n' 으로 제한됨
  2. 최대 힙-화 연산을 적용하기 위한 전제 조건으로서 '최대 힙 특성을 위반한 요소가 하나만(a single violation) 존재하는 힙' 을 입력으로 받음을 가정하고 있음  -->  각 단계에서 O(1) 의 복잡도 가짐

 

* 최대 힙 구축 (build_max_heap) in detail

• 임의의 배열 A[1:n]  -->  최대 힙 구조로 변환(convert) 하는 알고리즘

# pseudo-code for now
def build_max_heap(A, i):
    for i = (n/2) down to 1:
        do max_heapify(A, i)

• n 이 아닌 n/2 부터 for 문을 도는 이유? :  (n/2+1) ~ n 번째 노드는 모두 단말 노드(leaves) 에 해당하기 때문에 이미 최대 힙 특성을 만족하고 있음!
• 복잡도(Complexity)
  1. 언뜻 생각하면 O(n log n) : max_heapify 의 복잡도 O(log n) * n/2 단계 = O(n log n)
  2. 잘 분석해보면 O(n) : 트리의 높이가 올라갈수록 (루트에 가까워질수록) 서브트리가 점점 커지므로 개별 노드에서 일어나는 연산은 증가하지만, 노드의 개수 자체는 줄어든다는 점이 포인트!

 

 

* 힙 정렬 (Heap sort)

• 최대 / 최소 힙 특성을 이용한 정렬! build_max_heap() 만 반복하면 됨...

1. 정렬되지 않은 배열 A 를 최대 힙(max_heap) 으로 변환함  __ O(n)
2. 최댓값 A[1] (== 루트) 를 찾음  __ O(1)
3. 최댓값 A[1] 을 n번째 요소 A[n] 와 교환(swap) 함 (최댓값을 n번째 노드로 보내기!)  __ O(1)
4. n번째 노드를 버리고 (== 최댓값 추출) 힙 크기를 n-1 로 줄임  __ O(1) 
5. (3) 에 의해 루트에 최댓값이 위치하지 않게 되어 최대 힙 특성이 위배되고 있을 것이므로 & 나머지 서브트리는 여전히 최대 힙 특성을 유지하고 있으므로 max_heapify() 를 적용하여 다시 최대 힙으로 만듦  __ O(log n)
6. 2~5 과정을 반복함  __ n steps

• 복잡도(Complexity): O(log n) * n steps = O(n log n)