알고리즘 이론 6강. 힙 정렬(Heap Sort)

 

[힙 정렬(Heap Sort)]

: 병합정렬과 삽입정렬의 장점 결합 (실행시간 O(nlogn), 추가적인 기억장치 필요 X)

 

 

[이진트리의 종류]

1. 정 이진 트리(Full Binary Tree)

: 잎 노드가 아닌 노드 전부가 최대 2개의 자식노드를 가지는 트리

 

2. 완전 이진 트리(Complete Binary Tree)

: 트리의 마지막 레벨을 제외한 레벨이 완전히 꽉차고, 마지막 레벨에서 노드들이 왼쪽부터 채워진 트리

정 이진 트리와 완전 이진 트리 예시

3. 거의 완전 이진 트리(Nearly Complete Binary Tree)

: 완전 이진트리 직전의 트리(노드 한개가 부족.. 등)

 

 

[거의 완전 이진 트리 배열 구현]

: 논리적으로는 이진 트리지만, 물리적으로는 선형 배열의 형태

# 주요 속성 (A : 트리 배열, i : 특정 노드의 index)

- 트리의 루트(root) : A[1]

- 특정 노드의 부모 노드 index : floor(i/2)

- 특정 노드의 왼쪽 자식 노드 index : 2i

- 특정 노드의 오른쪽 자식 노드 index : 2i+1

 

 

[이진 힙의 종류]

- Max-heap(최대 힙) : 자식 노드의 값이 부모 노드의 값보다 무조건 작은 힙(트리 위일수록 큰 값)

- Min-heap(최소 힙) : 자식 노드의 값이 부모 노드의 값보다 무조건 큰 힙(트리 위일수록 작은 값)

: 여기서 중요한건, 같은 레벨의 노드간에 크고작음은 상관 없다는 것!

 

 

[이진 힙의 특징]

: 노드의 개수(배열의 길이)가 n개 일때.

- 힙의 높이 : floor(logn)

- 잎 노드의 개수 : ceil(n/2)

- 높이 h에서의 노드의 개수 : <= ceil(n/2^(h+1))

 

 

---

 

[힙의 5가지 기본 절차]

1. HEAPIFY : 힙 속성 흭득

2. BUILD-HEAP : 정렬되지 않은 배열로부터 힙 생성

3. HEAPSORT : 힙 배열 정렬

4. EXTRACT-MAX : 최대값 선택 추출

5. INSERT : 새로운 값 힙에 삽입

 

 

[MAX-HEAPIFY(A,i)]

: 최대 힙 특성 유지하기 위해 i번째 원소를 힙 배열 A내 올바른 위치에 오게끔 하는 절차

 

MAXHEAPIFY(A,i):                          # Max-heap : 값이 클수록 위에 위치
  l = left(i)                             # index i의 왼쪽 자식 노드 index
  r = right(i)
  if l <= len(A) and A[l] > A[i]:         # 현재 i의 값이 왼쪽 자식 노드의 값보다 작으면,
    largest = l                           # 큰 값의 index를 largest에 저장
  else:
    largest = i             
  if r <= len(A) and A[r] > A[largest]:   # 오른 자식 노드의 값이 largest값 보다 크면
    largest = r                           # 교체
 
  if largest != i                         # 현재,자식(왼,오)중 가장 큰 값과 자리 교체
    A[i], A[largest] = A[largest], A[i]  
 
   MAXHEAPIFY(A,largest)                  # 교체 안일어 날때까지 반복

MAX-HEAPIFY 예시

(a) MAX-HEAPIFY(A, 2) : 교체 발생해서 재귀

(b) MAX-HEAPIFY(A, 4) : 교체 발생해서 재귀

(c) MAX0HEAPIFY(A, 9)

 

# MAX-HEAPIFY 시간 복잡도

: 트리 힙 배열 길이를 n이라 할때, 자식 서브 트리의 최대 크기는 2n/3이다.

- T(n) <= T(2n/3) + Θ(1)

- O(logn)

 

 

 

[BUILD-MAX-HEAP(A)]

: 배열 A를 최대 힙으로 바꾸는 과정

BUILD–MAX–HEAP(A):
  heap_size[A] <- length[A]
  for i = floor(length[A]/2) downto 1
    MAX–HEAPIFY(A,i)

: 배열의 A[n/2] 이후 부분은 잎노드이므로, 비교필요 없다.

 

# BUILD-MAX-HEAP의 시간복잡도

  : 시간복잡도 O(logn)인 MAX-HEAPIFY를 n번 호출 => O(nlogn)

  : 틀린건 아니지만 개선의 여지 있다(tight) => O(n)

 

 

 

[힙 정렬 알고리즘(Heap sort)]

: 힙(트리) 순으로 정렬된 배열을 배열에 크기순으로 정렬시키는 알고리즘

 

HEAPSORT(A):
  BUILD–MAX–HEAP(A)            # 배열 A를 힙 배열로 만든다
  for i = len(A) .. downto 2:
    A[1], A[i] = A[i], A[1]    # 제일 큰값(1) 루트값을 빼서 더이상 힙 배열 아닌 i번째로 삽입(공간절약)
    len(A) –= 1
    MAX–HEAPIFY(A,1)           # 최대값 빼고, 루트 원소 

: 추가적인 저장장치 (교환용 제외) 필요 없음

 

# Heap-sort 시간 복잡도

 : O(n) + O(n-1)*(O(1)+O(1)+O(logn))  =  O(nlogn)

 

 

 

[우선 순위 큐]

: 힙의 대중적인 응용중 하나

: 키값을 가진 원소들의 집합 S를 다루기 위한 자료구조.

# 기본적인 우선순위 큐 연산

1) INSERT(S, x) : 원소 x를 집합 S에 삽입

2) Maximum(S) : 집합 S에서 최대 key 값 원소를 반환

3) Extract-Max(S) : 집합 S에서 최대 key값 원소를 추출

4) Increase-Key(S,x,k) : 집합 S의 x원소의 key값을 k 로 변경