[computer science] Heap Sort와 Priority Queue

이 게시글은

서울대학교 데이터사이언스대학원

조요한 교수님의

데이터사이언스 응용을 위한 컴퓨팅 강의를

학습을 위해 재구성하였습니다.

---

이전 시간에 이어 이번에는

Heap Sort와 Prioirity Queue 내용을

정리해보려고한다

 

 

Heap Sort

 

Heap Sort는 유명한 정렬 알고리즘 중 하나이다

정렬이 되지 않은 array를 heap을 바탕으로

정렬을 시키는 방식이다

 

이 과정을 수행하기 위해서는

우선 array에 build_max_heap을

적용시켜줘야한다

 

하지만 위 ppt만 봐도 알겠지만

build_max_heap만 했다고

그 array가 정렬이 되는 것은 아니다

 

우선 build_max_heap을 시켜준다음

subarray에 대해서 계속

max_heapify를 해줘야한다

이게 무슨 말인지 자세히 살펴보자

 

 

정렬이 안된 array에 build_max_heap을 적용하면

0번째 index인 root node가

해당 array에서 가장 큰 값을 갖고있다는 것은 알 수 있다

 

따라서 이미 root, 즉 0번째 index는 이미

정렬이 완료되었다고 생각한 뒤

가장 뒤의 노드와 root node를 교체해준다

 

그러면 root node였던 16은 max heap에서

가장 끝 node로 가게된다

그런 뒤 그냥 그 노드의 연결을 끊어준다

 

그런 다음 맨 마지막 값을 제외한

나머지를 subarray로 두고

max_heapify를 진행해준다

 

그런 다음 0에서 8번째 인덱스까지

max_heapify를 해주면

다시 root node에는

subarray에서 가장 큰 값이 오게 되고

root node를 가장 마지막 node와 교체해준다

그런 다음 0에서 7번째 index까지만

또 다시 subarray로 만들어서

max_heapify를 해주고

이 과정을 계속 반복해준다

 

 

마지막까지 해주면 정렬 완료

Heap Sort의 pseudo code를 살펴보자

 

처음에는 build_max_heap을 시켜준다

그런 다음 n-1부터 1까지 내려오면서

0번째와 i번째 node를 exchange해주고,

그 다음 heapSize를 한 개 줄여주고,

다시 max_heapify를 해준다

 

HeapSort 알고리즘의

time complexity를 보자

 

결론적으로 HeapSort는

O(n log n)만큼이 걸리는데

왜 이렇게 나오는지를 이해하려면

Big-O 표기법을 잘 이해하고있어야한다

 

우선, 이전 게시글에서 build_max_heapfiy의

time complexity가 O(n)이란걸 증명했다

 

그런 다음 n-1부터 1까지 총 n-1번에 대해서

max_heapify를 시켜주고

이전 게시글에서 max_heapfiy의 complexity는

O(log n)임을 배웠다

 

따라서 n-1번에 대해서 O(log n)의 시간이 걸리므로

(n-1) * O(log n)만큼이 소요되는 것이지만,

Big-O 표기법의 정의를 잘 이해해야한다

 

Big-O 표기법은 데이터의 개수 n개에 대해서

알고리즘을 수행했을 때 걸리는 시간이

얼마나 빠르게 증가하는지를 보기위한 표기법이다

 

따라서 Big-O 표기법으로 time complexity를 계산할 때는

n, n-1, n+1와 같이 상수는 고려를 해주지 않는다

n이 증가함에 따라 총 시간이 얼마나 빠르게 증가하는지를

보여주기 위한 계산에서 상수는 그다지 중요한 요소가 아니기 때문이다

 

따라서 (n-1) * O(log n)이지만

결국 이는 n * O(log n)만큼 걸린다고

표기를 해주는 것이다

 

그렇다면 build_max_heap인 O(n)과

그 뒤의 과정인 n *O(log n) = O(n log n)을 더한

O(n) + O(n log n)이 된다

 

하지만 여기서 또 Big-O 표기법의 정의를 이해해야한다

Big-O 표기법은 결국 n이 무한대로 갔을 때

어느정도의 기울기로 수행 속도가 증가하는지를 측정한다

 

n의 개수가 적을 때는 O(n)의 수행속도가 더 크겠지만

n이 무한대로 증가할수록 O(n logn)의 수행속도가

현저하게 더 커지는 것을 확인할 수 있다

 

따라서, Big-O 표기법에서는 앞의

O(n)은 크게 의미가 없어지는 것이다

 

그래서 보통 Big-O 표기법을 계산해 줄 때

항이 2개 이상이면 둘 중 증가 속도가 더 큰 항만

살리고 나머지 항은 제거해준다

 

이에 따라, O(n)은 빅오 표기법에 의해 무시가 되고

O(n log n)만 남게되어서

최종적으로 HeapSort 알고리즘의 time complexity는

O(n log n)이 되는 것이다

 

 

 

Priority Queue

 

 

이제는 priority queue에 대한 내용을

정리해보고자 한다

 

Priority Queue는 우리가 흔히 아는

자료구조 Queue의 형태인데

각 Queue마다 priority가 있어서

priority가 높은 queue가 먼저 dequeue가 되는

queue를 말한다

 

 

이런 Priority Queue는 많은 곳에서 쓰이는데

119와 같은 emergency call에서

전화가 빨리 들어온 순서보다는

중요한 전화를 순서대로 처리할 때 사용하기도하고

 

운영체제 강의를 듣다보면 배우게되는

job scheduling에서도 사용된다

 

그런 다음, 우리가 다음 시간에 배우게 될..

path finding에서도 사용된다

 

 

이런 priority queue를 구현할 때는

max heap으로 구현하는 것이

가장 자연스러운 선택지가 될 수 있다

 

insert(S, x, k) -> S set에 x를 k priority로 넣기

maximun(S) -> S set의 가장 Priority가 큰 element 반환

extract_max(S) -> maximum과 같은데 priority가 가장 높은걸 제거

increase_key -> element x의 priority를 k로 올려주기

 

위 4개 정도가 priority queue를 구현하는데

필요한 Operation이다

 

max heap으로 위 4개의 operation을

어떻게 구현할 수 있는지 하나씩 살펴보도록하자

 

위 operation 중에서 maximum의 pseduo code이다

0번째 index, 즉 root 노드만 반환해주면되므로

시간복잡도는 O(1)이 된다

 

 

그 다음은 extract_map이다

 

위 maximum과 동일한 데

root node를 제거한 뒤, 그 다음 node들을

max heap으로 다시 만들어줘야한다

 

heapSize는 1개가 줄어들고

가장 마지막에 있던 node와 root node를

서로 교체해준 뒤

위치가 바뀐 root node는 제거하고

0번째 index에 대해서

max_heapify를 진행해준다

 

pseudo code이다

 

max는 max_heap_maximum opeartion으로

설정해준 다음, 해당 Node를 가장 마지막 node와 교체한다

 

그런 다음 heapSize를 1개 줄이고

max_heapfiy를 0번째 index에 대해서 진행해준다

 

시간복잡도는 max_heapify의 시간 복잡도인

O(log n)만큼 걸린다

 

 

increase_key operation의 구현이다

 

특정 node의 priority를 올려주면

max heap이 깨질 수가 있다

 

위의 경우에도 7을 22로 올려주니

max heap의 구조가 깨졌기 때문에

parent node와 교체하는 모습을 볼 수 있다

 

 

pseudo code를 살펴보자

 

increase_key는 priority을 올려주는 것이기 때문에

기존의 Priority보다 올려줄 값이 작다면

에러를 반환한다

 

그런 다음 x의 priority를 k로 해준 뒤

i가 0보다 크고, i의 priority가 그 부모의 priority보다

큰 경우일 때, 두 node의 값을 교체해준다

 

그런다음 Index i를 부모의 index로 교체한 뒤

while문을 통해 i가 0이 될 때까지 반복해준다

 

increase_key는 priority가 기존보다

커지는 것이기 때문에

priority가 변경되는 Node보다

앞 index의 node들만 고려해주면 되기 때문이다

 

time complexity는 O(log n)이 된다고한다

 

 

마지막으로 insert를 보자

 

만약 heap overflow가 발생하면 error를 띄어주고

그렇지 않다면 heapsize를 1 증가시켜준다

 

k는 우선 x.key값, 즉 새로 추가할 node의 priority값이고

x.key에는 -무한대를 할당해준다

그런 다음 가장 마지막에 x를 추가해준다

 

그런 뒤, 가장 마지막에 추가한 node x에 대해서

원래 priority인 k만큼

max_heap_increase_key를 해주면 된다

 

이는 n에 영향을 받는게

max_heap_increase_key밖에 없으므로

시간 복잡도는 increase_key와 같은 O(log n)이 된다

 

 

 

이렇게 2개의 게시글에 걸쳐서

binary tree, max heap, heap sort, priority queue까지 정리 마무리 -!

 

개발을 하면서 들어본 내용이었는데도

이렇게 제대로 배우니 조금 헷갈리는 감이 있어

꾸준히 봐줘야겠다고 생각했다