[Introduction to Algorithm] 4. Heaps and Heap Sort

4. Heaps and Heap Sort

Priority Queue

key를 가지는 각 요소를 가지는 집합이라고 볼수 있으며, 추가, 최대값, 최대값 추출, 키 값 변경등을 할수 있다.

Heap

Priority Queue의 Array 형식의 구현채로, 시각화하면 거의 완벽한 Binary Tree 형태를 가진다.

Max Heap Property 

주어진 node의 key 값은 항상 해당 node의 children node의 key 보다 항상 크다.

Min Heap 

Max Heap 과 반대의 특성을 가진다.

Heap as a Tree

root of tree : array의 첫번째 element. (i=1)
parent(i) = i/2 : node i 의 부모 node
left(i) = i*2 : node i의 왼쪽 child
right(i) = i*2+1 node i의 오른쪽 child

Binary Heap의 높이는 항상 O(lg n)

Heap Operation

build_max_heap : 정렬되지 않은 array를 max-heap 으로 변환하는 작업

max_heapify : max heap property를 하나만 어기는 경우, 이를 교정하는 작업

insert, extract_max,heapsort

Max_heapify 

* left(i) 와 right(i) 가 max-heaps 라고 가정.

* 만약 A[i] 가 max-heap property를 어긴다면, A[i]를 subtree의 root 와 바꿈으로써 교정할수 있다. 

Max_heapify (example)

Time = ? O(log n)

Max_Heapify Pseudocode

l = left(i)
r = right(i)

if ( l<= heap-size(A) and A[l] > A[i]) then largest = l else larges = i
if (r<= heap-size(A) and A[r] > A[largest]) then largest = r
if largest != i then exchange A[i] and A[largest] Max_Heapify(A, largest)

Build_Max_Heap(A)

for i=n/2 downto 1

    do Max_Heapify(A,i)

n/2 부터 시작하는 이유?

n/2+1....n까지는 Leaf Node 이고, Leaf Node 는 Single-Node Tree로 Max-Heap Property를 만족한다. 

Time =? O(n log n)

Build_Max_Heap(A) Analysis

Max_Heapify는 Leaf 바로위의 Node 에 대해서 O(1) 이 든다. 

일반화해서 보면  Leaf 보다 l level 만큼 떨어진 Node에 대해서는 O(l)이 든다고 할수 있다. 

level 1 nodes : n/4, level 2 node : n/8 .... level log n : 1개의 노드를 가진다고 할수 있다.

결과 적으로 총 loop count는

n/4(1c) + n/8(2c) + n/16(3c) .... 1 ( log n c)

n/4 = 2^k를 대입하면, 

c2^k(1/2^0 + 2/2^1 + 3/2^2 + .... (k+1)/2^k) 가 되면 () 은 수학적으로 상수(constant)가 된다. 

즉 cn/4*c' 가 되어 Build_Max_Heap은 O(n)을 가진다. 

Heap-Sort

1. Max Heap 생성 

2. 최대값 구하기 , A[1]

3. A[n] 과 A[1] 치환 

4. Heap 사이즈를 n-1로 변경 

5. max_heapify를 호출하여, Max Heap으로 재구성.

6. Heap 사이즈가 0이 될때 까지 2번부터 재시작.

* Running Time 

Heap이 비워질때 까지  n번의 loop 이 돌고 매 loop마다 max_heapify:O(log n) 이 호출된다.

즉, O(n log n)

영상 바로가기 :
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/

Heap Sort vs x-Sorts ?

Heap Sort 는 best,worst,average case에서 동일하다. 

Heap Sort 는 Memory Complexity 에서 모든 경우에 1을 가진다. 

Heap Sort는 Stable 하지 못한 Sorting 기법이다. 

* Sort에서 Stability 란, 중복된 key가 있는 입력 값에서 해당 key들이일정한 순서(원 입력의 순서)대로 정렬되는지를 의미한다.

https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms