L05 - Heapsort

 

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

 

 

Heapsort

 

Heapsort는 이름 그대로 Heap 자료구조를 활용하는 정렬 알고리즘이다!

 

=> Heap이란 Heap Property를 만족하는 Complete Binary Tree임!

 

(Complete Binary Tree란 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리 = 왼쪽이 비어있을 수 없음)

 

Heap Property

(Min-Heap의 경우) 각 노드의 값 <= 자식 노드의 값

(Max-Heap의 경우) 각 노드의 값 >= 자식 노드의 값

 

 

Max-Heap의 예시

 

 

=> Complete Binary Tree 이므로 위와 같이 배열로 구현이 가능함!

 

 

Heap Operations의 경우 (n은 Heap에 저장된 데이터 수)

Find-Max : θ(1) - 최댓값 찾기

Extract-Max(Sift down) : θ(log n) - 최댓값 지우기(Heap 유지하기)

Insert : θ(log n) - 값 넣기=> 밑에 붙이고 위로 올라가며 자리를 찾음

Build-Heap : θ(n) - Heap 만들기(Heap 구조를 따르게 바꿈)

 

 

그래서 결론적으로 Heapsort는

 

• 주어진 배열을 Complete Binary Tree로 봄
  
  
• Max-Heap Property를 만족하도록 Build-Heap을 수행함
  
  
• Extract-Max(= Swap 및 Sift down)를 반복하여 정렬

 

그림으로 살펴보면

 

 

Heapsort 흐름

 

 

 

처음 배열을 build_heap 할 때를 살펴보면

 

순차적으로 insert 한다고 하면 데이터를 트리의 높이만큼 순회하면서 삽입해야 하기 때문에 

log1 + log2 + log3 + ... + log(n-1) + logn 라고 볼 수 있고 이는 logn이 n개 있는 것보다 작거나 같을 수 밖에 없음

 

즉, <= nlogn 로 볼 수 있고 θ(nlogn) 임

이렇게 힙 구조를 따르게 배열을 바꿨으면 

 

Extract-max를 통해 가장 큰 값을 배열을 뽑아 맨 뒤로 보내며 힙을 유지하는 과정을 반복하며 정렬함

 

이 과정도 루트 노드와 마지막 리프 노드와 자리를 바꾸고 트리의 높이만큼 데이터를 순회하며 힙 구조를 유지하기 때문에
(이 때 루트 노드가 없어지므로 배열의 크기가 1씩 줄어듬)

 

logn + log(n-1) + log(n-2) + ... + log2 + log1 로 볼 수 있고 이는 logn이 n개 있는 것보다 작거나 같을 수 밖에 없음

 

즉, <= nlogn로 볼 수 있고 θ(nlogn) 임

 

그럼 build_heap을 하고 Extract-Max를 반복하는 과정을

합치면 결국 θ(nlogn)이 됨

 

Sift down

 

노드의 두 자식이 모두 Heap 일 때, 자식과 자신을 하나의 Heap으로 만드는 연산임

 

Sift Down 원리

 

 

왼쪽 그림을 보면 88이 부모노드이고 자식노드가 그 보다 작은 72, 48 이므로 Heap 구조인 것을 알 수 있음 (Max-Heap 기준)

 

85가 부모노드인 것도 마찬가지

 

하지만, 이 둘을 자식으로 갖는 부모 노드 6을 살펴보면 Heap 구조가 아니기 때문에 Sift down을 통해 이를 하나의 Heap으로 만드는 것을 볼 수 있음!

 

 

Sift Down 흐름

 

 

siftdown 하려는 노드를 기준으로 자식 노드들 중 더 큰 값을 가진 노드와 비교하여 만약 자식 노드가 더 클 경우 위치를 바꾸고

 

재귀적으로 siftdown을 하다가 리프 노드에 도달하거나 비교하려는 자식 노드보다 siftdown을 하는 노드가 값이 더 클 경우 중지함!

 

 

Extract-Max 흐름

 

 

그래서 다시 아까로 돌아가서 Heapsort의 흐름 중 Extract-Max 부분을 살펴보면

 

build_heap을 통해 Heap이 주어지면 Swap 및 Sift down 연산을 반복하여 정렬하는 것임!

 

 

Build-Heap

 

Build-Heap은 Sift down 연산을 뒤에서 부터 반복한다고 생각하면 됨

 

일단 Build-Heap은 Complete Binary Tree가 Heap Property를 만족하도록 값을 재배치함

 

위에서 말했다 싶이 순차적으로 insert 한다고 하면 O(nlogn) 인데, O(n)에 가능할까?

 

 

 

def build_heap(arr) :
	n = len(arr)
    for i in range(n//2 - 1, -1, -1) :
    	siftdown(i, arr, n)

 

 

그림과 같이 Heap이 아닌 노드부터 시작해서 (리프 노드도 노드가 아닌 Heap으로 볼 수 있음!)

 

Sift down 연산을 뒤에서부터 반복 적용하게 되면 θ(n)임

 

코드에서 siftdown을 n//2 - 1 에서 시작하는 이유


complete binary tree에서 internal node(리프 노드가 아닌 node) 중 가장 마지막 인덱스를 가르킴

 

 

Complexity Analysis of Build-Heap

 

 

정리를 해보자면

 

빈 Heap에 값을 하나씩 넣는건 

 

log1 + log2 + log3 + ... + log(n-1) + logn = θ(nlogn)

 

 

하지만, Sift down 연산을 뒤에서부터 반복 적용하면

 

 

Worst case 의 경우 θ(n)

 

1+ 1/2 + 1/2^2 + ... + 1/2^logn-1 부분에서 n이 무한대로 가는 등비 급수여도 2이기 때문에 2로 볼 수 있음

 

 

 

 

Best case 의 경우도 θ(n)

 

=> Sift down 을 n/2 회 수행하게 됨!

 

 

이므로 θ(n) 임!

 

 

따라서, Heapsort의 시간복잡도를 살펴보면

 

T(n) = θ(n) + θ(nlogn) = θ(nlogn)

 

여기서 앞의 θ(n)은 build-heap , θ(nlogn)은 swap, sift down을 의미함!