[컴퓨터 알고리즘 기초] 6. 힙 정렬 알고리즘

힙(heap) 정렬 알고리즘

힙 구조

- 힙의 형태

• 완전 이진 트리에 가까운 형태
• 이진트리는 각 노드의 자식수가 2이하인 경우
• 완전 이진트리는 Root 노드 부터 Leaf 노드까지 빠짐없이 채워져 있는 트리

 

- 최대힙 특성

• A[PARENT(i)]>=A[i]
  • 부모 노드의 값은 항상 자식 노드의 값보다 크다.
  • 따라서 전체 트리의 Root 노드값이 가장 크다.
  • 또한 각 하위 트리 구조의 Root 노드가 가장 큰 값을 가진다.

 

- 최소힙 특성

• A[PARENT(i)]<=A[i]
  • 자식 노드의 값은 항상 부모 노드의 값보다 크다.
  • 따라서 전체 트리의 Root 노드 값이 가장 잓다.
  • 또한 각 하위 트리 구조의 Root 노드가 가장 작은 값을 가진다.

 

- 힙의 배열 저장 방식

Root 노드는 배열의 첫 번째 A[1] 에 저장

각각의 노드들은 레벨별로 저장

 

* 힙을 배열에 저장하면 다음과 같이 검색이 가능하다.

• Parent(i) = i/2
• left(i) = 2i
• right(i) = 2i+1

 

- 노드의 높이

노드의 높이는 현재 노드에서 left노드까지 내려갈 때 가장 단순하게 내려가는 가장 긴 경로에서 거져야하는 간선의 수이다.

Root 노드로 부터 트리의 높이

• O(logn)
•  Heap은 완전 이진 트리 구조를 가지기 때문에 각 레벨 마다 노드의 수가 2배씩 증가하므로 높이는 O(logn)

 

힙 특성 관리

- Max-Heapify

노드가 입력으로 주어졌을때, 노드의 좌우 하위 트리들은 max-heap 특성을 유지하지만 노드의 값이 하위 트리 값보다 작거나 같아서 max-heap 특성을 만족하지 않을 때 max-heap 특성이 유지 되도록 바꾸는 연산

주어진 노드의 값을 "흘러내리게"해서 주어진 노드와 하위 트리가 max-heap 특성을 가질 수 있도록 변경

 

- Max-Heapify의 수행시간

• n을 하위 트리의 노드의 개수라고 할때
• 힙의 높이 O(h) =O(logn)
• 따라서 전체 수행기산은 O(logn) 시간

 

힙 구조 만들기

- Build-Max-Heap

build_max_heap(A)
    A.heap_size = A.length
    for i=[A.length/2] downto 1
        max_heapify(A,i)

 

- 힙 구조 만들기 수행 시간

수행 시간 분석

• Max-Heapify를 한번 호출 할 때 마다 O(logn)
• Max-Heapify의 호출 횟수는 O(n)
• 따라서 전체 수행 시간은 O(nlogn) 이 된다.

 

최대값 추출

- 최대값 추출(Extract-Max)

heap에서 가장 큰 값을 제거하고 Max-heap 구조를 복원하는 연산

 - 제일 큰 값(첫번째)을 뽑고 마지막에 있는 값을 첫번째 값으로 옮겨준다

 - 이후 heapify를 진행한다.

 

힙 소트

- 힙 소트(heap sort)의 Pseude code

heaposort(A)
    build_max_heap(A)
    for i=[A.length/2] downto 2
        exchange A[1] with A[i]
        A.heap_size = A.length - 1
        max_heapify(A,1)

 

- 힙 소트의 수행 시간

수행 시간 분석

• A[1...n]에 대해 Build_max_heap를 수행하는 시간 O(nlogn)
• extract-Max를 n번 반복
• 전체 수행시간 O(nlogn)