Week 3
이번주의 내용은 약간 더 방대하여 2번 나눠서 정리해보려 한다.
먼저 Priority Queues에 대해 설명하기 시작하며 여기서는 2진트리를 활용하여 개념을 잡는다.
이미 배운바와 같이 큐는 데이터 타입으로 FIFO의 형식을 갖추며 PushBack, PopFront의 API를 사용한다.
이에 확장된 개념으로 priority queue의 경우는 각 요소에 우선순위를 부여하여 그 순서에 맞게 배치하는 것을 말한다.
이는 정해진 우선순위에 따른 스케쥴을 관리할 때에 주로 사용된다고 한다. 일을 하나씩 처리하고 있을 때 다음 업무를 추가할 때 Insert를 통해 진행하며 중요도가 높은 업무는 ExtractMax를 통해 진행할 수 있다.
정의를 살펴보자면 위에서 언급한 것과 대동소이하며 Insert, ExtractMax의 주요 동작을 통해 각 요소의 우선순위를 제어하는 데이터 타입이다.
바로 예시를 들어가면 Insert(5), Insert(4), Insert(1), Insert(7)을 통해 요소들을 입력시킨 뒤 저장이 된 상태이다. 이 때 중요한 점은 현재상태에서는 우선순위는 전혀 정해진 바가 없으며 앞으로 ExtractMax를 통해서 불러낼 때부터가 중요하다.
위와 같이 ExtractMax를 통해 priority queue에서 찾게 되면 7이 될 것이며,
바로 빠져나가는 것을 볼 수 있다.
Insert(3)를 통해 priority queue에 3을 입력하고,
다시금 ExtractMax를 호출하면 다음 최대값인 5가 빠져나가게 된다.
이후에도 같은 프로세스로 진행이 되는 것을 알 수 있다.
바로 퀴즈가 나오는데 어렵지 않게 풀 수 있다. (18 14 15 12 10)
추가적으로 위와 같은 API들이 있음을 소개한다. Remove는 제거를, GetMax는 ExtractMax와 달리 priority queue에서 빼내가지 않고 최고 우선순위인 요소를 찾기를, ChangePriority는 지정 요소의 우선순위를 변경하기를 지원한다.
여기에는 priority queue를 사용하는 4가지 방법이 있음을 알려주며 마지막인 heap sort를 다음에 더 자세히 배워볼 것이다.
우선 Unsorted array나 list에 priority queue를 적용해본다. Insert의 경우 단순히 끝자락에 이어주면 끝이나며 복잡도는 O(1)인 것을 알 수 있다.
ExtractMax의 경우 먼저 array/list를 한번 스캔 후 해당 원소를 반환 후 다시 재배열하므로 복잡도는 O(n)이 된다.
Sorted Array에서는 약간 달라지는데 우선순위가 오름차순으로 정렬이 되어있으므로 ExtractMax는 최종원소이며 바로 추출하는 것이 가능하다.
위와 같이 Insert는 해당 위치를 찾아서 원소들을 옮긴 후 입력하게 된다.
Sorted List의 경우에는 ExtractMax가 Sorted Array처럼 최우측에 있는 값을 뽑아내기만 하면 되고 Insert는 해당 위치를 찾은 후 포인터들을 다시금 삽입하는 원소에 연결시키고 기존 연결을 끊으면 된다.
이들의 복잡도는 각각 O(1)과 O(n)이다.
어떤 어플리케이션이 있을 때 Insert를 n번 호출하고 ExtractMax를 루트 n번 호출한다면 array가 좋을지 sorted array가 좋을지 선택하는 문항이다. 해설과 같은 이유로 그냥 array가 더 효율적이다.
Binary max heap에 대한 정의이며 이번에 사용하는 binary tree는 약간 다른 형태를 띄게 된다.
위와 같은 케이스는 온전한 heap이 아니며,
퀴즈가 나오는데 이 또한 온전한 heap의 형태가 아니다. (자세하게는 밑에서 여러 예시들로 구분할 수 있다)
다음강의로 넘어가기전 height의 정의가 달라짐에 대해 설명하며 예시를 들고 있다.
GetMax 동작을 설명하는데 단순히 최우선순위에 해당되는 최상위원소를 반환하며,
Insert는 말그대로 삽입하는 동작을 말한다.
SiftUp은 방금 삽입한 32가 부모노드와 우선순위가 맞지 않기 때문에 위로 올려주는 동작이며,
이후에도 부모노드인 29와 비교했을 때도 순위가 맞지 않으므로 또다시 SiftUp을 진행한다.
이때의 복잡도는 O(tree height)이 된다.
위에서 본 Heap의 전반적인 내용과 같이 원소가 추가될 때마다 tree의 구조가 발달하고 이는 곧 height의 변화를 가져온다. 그러므로 height의 복잡도는 O(n)이 된다.
ExtractMax는 최상단의 우선순위가 높은 원소를 추출하게 되는데,
위와 같이 root를 아무 leaf나 선택한 후,
Max값은 빼내고 선택한 leaf가 최상단에 위치하게 된다.
이후 SiftDown동작이 일어나는 것을 설명하는데 leaf에서 온 원소이기 때문에 자식 노드들과 비교했을때 위치가 맞지 않게된다.
따라서 자식 노드를 선정하고,
자리를 바꾸며 또 자식노드와 비교했을 때 적절치 못하므로 14와 바꾸게 된다.
그렇게 맞는 자리를 찾아가기까지 복잡도 O(tree height)가 소요된다.
ChangePriority에 대한 설명인데 만약 leaf인 12를,
35로 변환한다면,
SiftUp 작용이 일어나게 되고,
맞는 자리를 찾아가게 될 것이다.
이 또한 O(tree height)의 복잡도를 가진다.
Remove를 하기 위해 18을 선택 후,
그 우선순위를 무한대로 변경한다.
SiftUp을 통해 최상단으로 보낸 후
ExtractMax를 통해
leaf인 11이 최상단에 위치하면서,
무한대를 삭제하게 된다.
이후 SiftDown을 통해 적합한 자리를 다시 찾아가게 되고,
안정화 될 때까지 이동 후,
Remove를 마치게 된다.
복잡도는 O(tree height)이 된다.
Summary에서는 GetMax만 O(1)이고 나머지 동작들은 모두 O(tree height)임을 정리해준다.
그렇다면 우리는 tree height이 얕기를 갈망하고 그렇게 만들기 위해서는 온전한 tree모양을 정의할 필요가 있는데 아래의 예시들을 통해 알 수 있다.
온전한 트리
온전한 트리
온전한 트리
온전한 트리
온전하지 못한 트리
온전하지 못한 트리
온전하지 못한 트리이고 이제까지 봤던 예시들을 토대로 트리가 온전하기 위해서는 각 세대가 왼쪽부터 모두 순서대로 차있어야 된다. 그래야 트리의 높이가 얕게 유지될 수 있다.
위의 온전한 트리의 장점은 당연히 얕은 높이가 되겠으며 n개의 노드를 가질 때 높이는 최대 O(log n)가 된다.
증명이며 이에 대한 예시로 첫번째 트리는 n이 10, l이 4이고,
두번째 트리는 n이 15, l은 같을 때 위의 수식에 부합함을 알 수 있다.
두번째 장점은 마치 array처럼 저장이 가능하다는 점이다.
이 두가지의 장점을 위해서는 트리를 온전하게 유지하는 것이 중요하며 트리의 모양을 수정하는 것은 Insert와 ExtractMax임을 알려준다.
이제는 온전한 트리상태로 각기 다른 동작을 시험해본다. 30을 Insert한 뒤,
SiftUp을 통해 14와 위치를 바꾸며,
29와도 위치를 변경하여 온전한 트리를 유지한다.
ExtractMax도 마지막 원소이자 리프인 14를 선택하고 Max값을 추출한 뒤 14를 최상단으로 올리며,
이 상태에서 SiftDown을 진행한다.
알맞은 우선순위에 배치될 때까지 반복하여 내려가며
적정한 자리로 왔을 때 끝나게 된다.
maxSize는heap에 존재하는 원소의 최대갯수를 말하고, size는 heap의 크기, H는 힙이 첫크기원소들을 차지하고 있는 배열 이라고 하는데 바로 예시를 보면,
위와 같이 트리에 13까지 있을 때 size는 9, 배열을 통해 13까지 증가할 수 있으므로 maxSize가 13, 그리고 이 배열이 H가 된다.
이제까지의 내용을 정리한 것이며 먼저 Parent, LeftChild, RightChild의 연산이 나오고
SiftUp의 pseudocode,
SiftDown의 pseudocode,
Insert의 pseudocode,
ExtractMax pseudocode,
Remove pseudocode,
ChangePriority pseudocode를 보여준다.
다음은 HeapSort에 대해 배우게되고 위에서 보듯 HeapSort에 대한 pseudocode를 확인할 수 있다.
이 알고리즘은 비교 기반이며 복잡도는 O(n log n)이라고 한다.(점진적으로 최적값에 도달하는)
우선 BuildHeap의 pseudocode를 살펴보면 갯수가 size가 되어 n/2이 1이 될 때까지 SiftDown을 진행하는 것이며,
만약 n이 15라고 할 때 위와 같은 구조로 heap을 생성할 수 있게 된다.
그럼 맨 오른쪽 7번 노드에서 subtree부터 온전한지 여부를 검사하고 완성이 되면 옆의 6번 노드의 subtree, 이 후 5, 4, 3, ... 순서대로 비교하며 온전하지 않을 경우 SiftDown을 진행한다.
위의 순서들을 다시금 글로 옮긴 것이며 마지막으로 복잡도가 O(n log n)임을 시사하며 넘어간다.
이제 HeapSort로 넘어가서 pseudocode를 보는데 위의 순서대로 진행이 되며 이의 장점은 다른 공간이 필요없이 최적화된 빠른 알고리즘이라고 설명한다.
또한 Building Running Time에 대해 언급하며 BuildHeap의 작동시간에 대해 평가하는 것이 비관적인지 물음을 던지며 설명을 시작한다.
node의 갯수와 SiftDown의 running time을 기재하며 BuildHeap의 running time의 수식을 정리하고 있다. node가 n/2일 경우 T(SiftDown)은 1이며 n/4는 2, n/8은 3과 같이 진행이 되는데 이는 부모세대로 올라갈수록 복잡도가 하나씩 증가함을 의미한다.
그리고 무한급수가 어떤값에 수렴하는지 증명을 통해 보여주고 이를 통해 T(BuildHeap)이 2n이하임을 알 수 있다.
Partial sorting에 대한 내용도 나오는데 HeapSort를 위의 방식으로만 진행한다면 Time이 선형적으로 증가할 수 밖에 없는 구조이기에 k가 너무 크지 않은 상황에서 Partial sorting을 통해 어느정도 해결할 수 있다고 한다.
그래서 모든 배열을 재조정할 필요없이 해결이 가능하게되며 이에 대한 Running time은 O(n + k log n)이 된다.
결론적으로 Heap sort 알고리즘은 시간과 공간을 효율적으로 사용하는 비교 기반의 알고리즘이다.
마지막으로 Final Remarks에서는 위에서 트리에 대해 언급할 때 1부터 시작하는 것과 달리 배열은 0부터 시작하기 때문에 Parent, LeftChild, RightChild의 수식이 위와 같이 변경되는 것을 알려준다.
Min-Heap이라는 개념도 추가적으로 설명하며 이는 subtree와 비슷한 개념이다.
d-ary Heap이라는 개념을 통해 이제까지의 Heap에 대해 일반화가 가능해짐을 명시하면서 특징들을 말한다. 우선 각 노드는 최대 d개의 자식 노드를 가질 수 있고, 높이는 logdn이 된다. 그리고 SiftDown의 복잡도가 SiftUp보다 큰 이유는 온전한 트리를 완성하기 위해 어느쪽으로 내려갈지 비교해야하기 때문이다.
마무리로 Summary를 보여주면서 정리한다.
이번주의 내용은 약간 더 방대하여 2번 나눠서 정리해보려 한다.
먼저 Priority Queues에 대해 설명하기 시작하며 여기서는 2진트리를 활용하여 개념을 잡는다.
이미 배운바와 같이 큐는 데이터 타입으로 FIFO의 형식을 갖추며 PushBack, PopFront의 API를 사용한다.
이에 확장된 개념으로 priority queue의 경우는 각 요소에 우선순위를 부여하여 그 순서에 맞게 배치하는 것을 말한다.
이는 정해진 우선순위에 따른 스케쥴을 관리할 때에 주로 사용된다고 한다. 일을 하나씩 처리하고 있을 때 다음 업무를 추가할 때 Insert를 통해 진행하며 중요도가 높은 업무는 ExtractMax를 통해 진행할 수 있다.
정의를 살펴보자면 위에서 언급한 것과 대동소이하며 Insert, ExtractMax의 주요 동작을 통해 각 요소의 우선순위를 제어하는 데이터 타입이다.
바로 예시를 들어가면 Insert(5), Insert(4), Insert(1), Insert(7)을 통해 요소들을 입력시킨 뒤 저장이 된 상태이다. 이 때 중요한 점은 현재상태에서는 우선순위는 전혀 정해진 바가 없으며 앞으로 ExtractMax를 통해서 불러낼 때부터가 중요하다.
위와 같이 ExtractMax를 통해 priority queue에서 찾게 되면 7이 될 것이며,
바로 빠져나가는 것을 볼 수 있다.
Insert(3)를 통해 priority queue에 3을 입력하고,
다시금 ExtractMax를 호출하면 다음 최대값인 5가 빠져나가게 된다.
이후에도 같은 프로세스로 진행이 되는 것을 알 수 있다.
바로 퀴즈가 나오는데 어렵지 않게 풀 수 있다. (18 14 15 12 10)
추가적으로 위와 같은 API들이 있음을 소개한다. Remove는 제거를, GetMax는 ExtractMax와 달리 priority queue에서 빼내가지 않고 최고 우선순위인 요소를 찾기를, ChangePriority는 지정 요소의 우선순위를 변경하기를 지원한다.
여기에는 priority queue를 사용하는 4가지 방법이 있음을 알려주며 마지막인 heap sort를 다음에 더 자세히 배워볼 것이다.
우선 Unsorted array나 list에 priority queue를 적용해본다. Insert의 경우 단순히 끝자락에 이어주면 끝이나며 복잡도는 O(1)인 것을 알 수 있다.
ExtractMax의 경우 먼저 array/list를 한번 스캔 후 해당 원소를 반환 후 다시 재배열하므로 복잡도는 O(n)이 된다.
Sorted Array에서는 약간 달라지는데 우선순위가 오름차순으로 정렬이 되어있으므로 ExtractMax는 최종원소이며 바로 추출하는 것이 가능하다.
위와 같이 Insert는 해당 위치를 찾아서 원소들을 옮긴 후 입력하게 된다.
Sorted List의 경우에는 ExtractMax가 Sorted Array처럼 최우측에 있는 값을 뽑아내기만 하면 되고 Insert는 해당 위치를 찾은 후 포인터들을 다시금 삽입하는 원소에 연결시키고 기존 연결을 끊으면 된다.
이들의 복잡도는 각각 O(1)과 O(n)이다.
어떤 어플리케이션이 있을 때 Insert를 n번 호출하고 ExtractMax를 루트 n번 호출한다면 array가 좋을지 sorted array가 좋을지 선택하는 문항이다. 해설과 같은 이유로 그냥 array가 더 효율적이다.
Summary이며 추가적으로 Binary heap의 Insert와 ExtractMax에 대한 내용이 있는데 이는 다음 내용에 설명된다.
Binary max heap에 대한 정의이며 이번에 사용하는 binary tree는 약간 다른 형태를 띄게 된다.
위와 같은 케이스는 온전한 heap이 아니며,
퀴즈가 나오는데 이 또한 온전한 heap의 형태가 아니다. (자세하게는 밑에서 여러 예시들로 구분할 수 있다)
다음강의로 넘어가기전 height의 정의가 달라짐에 대해 설명하며 예시를 들고 있다.
GetMax 동작을 설명하는데 단순히 최우선순위에 해당되는 최상위원소를 반환하며,
Insert는 말그대로 삽입하는 동작을 말한다.
SiftUp은 방금 삽입한 32가 부모노드와 우선순위가 맞지 않기 때문에 위로 올려주는 동작이며,
이후에도 부모노드인 29와 비교했을 때도 순위가 맞지 않으므로 또다시 SiftUp을 진행한다.
이때의 복잡도는 O(tree height)이 된다.
위에서 본 Heap의 전반적인 내용과 같이 원소가 추가될 때마다 tree의 구조가 발달하고 이는 곧 height의 변화를 가져온다. 그러므로 height의 복잡도는 O(n)이 된다.
ExtractMax는 최상단의 우선순위가 높은 원소를 추출하게 되는데,
위와 같이 root를 아무 leaf나 선택한 후,
Max값은 빼내고 선택한 leaf가 최상단에 위치하게 된다.
이후 SiftDown동작이 일어나는 것을 설명하는데 leaf에서 온 원소이기 때문에 자식 노드들과 비교했을때 위치가 맞지 않게된다.
따라서 자식 노드를 선정하고,
자리를 바꾸며 또 자식노드와 비교했을 때 적절치 못하므로 14와 바꾸게 된다.
그렇게 맞는 자리를 찾아가기까지 복잡도 O(tree height)가 소요된다.
ChangePriority에 대한 설명인데 만약 leaf인 12를,
35로 변환한다면,
SiftUp 작용이 일어나게 되고,
맞는 자리를 찾아가게 될 것이다.
이 또한 O(tree height)의 복잡도를 가진다.
Remove를 하기 위해 18을 선택 후,
그 우선순위를 무한대로 변경한다.
SiftUp을 통해 최상단으로 보낸 후
ExtractMax를 통해
leaf인 11이 최상단에 위치하면서,
무한대를 삭제하게 된다.
이후 SiftDown을 통해 적합한 자리를 다시 찾아가게 되고,
안정화 될 때까지 이동 후,
복잡도는 O(tree height)이 된다.
Summary에서는 GetMax만 O(1)이고 나머지 동작들은 모두 O(tree height)임을 정리해준다.
그렇다면 우리는 tree height이 얕기를 갈망하고 그렇게 만들기 위해서는 온전한 tree모양을 정의할 필요가 있는데 아래의 예시들을 통해 알 수 있다.
온전한 트리
온전한 트리
온전한 트리
온전한 트리
온전하지 못한 트리
온전하지 못한 트리
온전하지 못한 트리이고 이제까지 봤던 예시들을 토대로 트리가 온전하기 위해서는 각 세대가 왼쪽부터 모두 순서대로 차있어야 된다. 그래야 트리의 높이가 얕게 유지될 수 있다.
위의 온전한 트리의 장점은 당연히 얕은 높이가 되겠으며 n개의 노드를 가질 때 높이는 최대 O(log n)가 된다.
증명이며 이에 대한 예시로 첫번째 트리는 n이 10, l이 4이고,
두번째 트리는 n이 15, l은 같을 때 위의 수식에 부합함을 알 수 있다.
두번째 장점은 마치 array처럼 저장이 가능하다는 점이다.
이 두가지의 장점을 위해서는 트리를 온전하게 유지하는 것이 중요하며 트리의 모양을 수정하는 것은 Insert와 ExtractMax임을 알려준다.
이제는 온전한 트리상태로 각기 다른 동작을 시험해본다. 30을 Insert한 뒤,
SiftUp을 통해 14와 위치를 바꾸며,
29와도 위치를 변경하여 온전한 트리를 유지한다.
ExtractMax도 마지막 원소이자 리프인 14를 선택하고 Max값을 추출한 뒤 14를 최상단으로 올리며,
이 상태에서 SiftDown을 진행한다.
알맞은 우선순위에 배치될 때까지 반복하여 내려가며
적정한 자리로 왔을 때 끝나게 된다.
maxSize는heap에 존재하는 원소의 최대갯수를 말하고, size는 heap의 크기, H는 힙이 첫크기원소들을 차지하고 있는 배열 이라고 하는데 바로 예시를 보면,
위와 같이 트리에 13까지 있을 때 size는 9, 배열을 통해 13까지 증가할 수 있으므로 maxSize가 13, 그리고 이 배열이 H가 된다.
이제까지의 내용을 정리한 것이며 먼저 Parent, LeftChild, RightChild의 연산이 나오고
SiftUp의 pseudocode,
SiftDown의 pseudocode,
Insert의 pseudocode,
ExtractMax pseudocode,
Remove pseudocode,
ChangePriority pseudocode를 보여준다.
Summary에서 온전한 트리를 시행할때의 장점을 다시금 언급한다.
다음은 HeapSort에 대해 배우게되고 위에서 보듯 HeapSort에 대한 pseudocode를 확인할 수 있다.
이 알고리즘은 비교 기반이며 복잡도는 O(n log n)이라고 한다.(점진적으로 최적값에 도달하는)
우선 BuildHeap의 pseudocode를 살펴보면 갯수가 size가 되어 n/2이 1이 될 때까지 SiftDown을 진행하는 것이며,
만약 n이 15라고 할 때 위와 같은 구조로 heap을 생성할 수 있게 된다.
그럼 맨 오른쪽 7번 노드에서 subtree부터 온전한지 여부를 검사하고 완성이 되면 옆의 6번 노드의 subtree, 이 후 5, 4, 3, ... 순서대로 비교하며 온전하지 않을 경우 SiftDown을 진행한다.
위의 순서들을 다시금 글로 옮긴 것이며 마지막으로 복잡도가 O(n log n)임을 시사하며 넘어간다.
이제 HeapSort로 넘어가서 pseudocode를 보는데 위의 순서대로 진행이 되며 이의 장점은 다른 공간이 필요없이 최적화된 빠른 알고리즘이라고 설명한다.
또한 Building Running Time에 대해 언급하며 BuildHeap의 작동시간에 대해 평가하는 것이 비관적인지 물음을 던지며 설명을 시작한다.
node의 갯수와 SiftDown의 running time을 기재하며 BuildHeap의 running time의 수식을 정리하고 있다. node가 n/2일 경우 T(SiftDown)은 1이며 n/4는 2, n/8은 3과 같이 진행이 되는데 이는 부모세대로 올라갈수록 복잡도가 하나씩 증가함을 의미한다.
그리고 무한급수가 어떤값에 수렴하는지 증명을 통해 보여주고 이를 통해 T(BuildHeap)이 2n이하임을 알 수 있다.
Partial sorting에 대한 내용도 나오는데 HeapSort를 위의 방식으로만 진행한다면 Time이 선형적으로 증가할 수 밖에 없는 구조이기에 k가 너무 크지 않은 상황에서 Partial sorting을 통해 어느정도 해결할 수 있다고 한다.
그래서 모든 배열을 재조정할 필요없이 해결이 가능하게되며 이에 대한 Running time은 O(n + k log n)이 된다.
결론적으로 Heap sort 알고리즘은 시간과 공간을 효율적으로 사용하는 비교 기반의 알고리즘이다.
마지막으로 Final Remarks에서는 위에서 트리에 대해 언급할 때 1부터 시작하는 것과 달리 배열은 0부터 시작하기 때문에 Parent, LeftChild, RightChild의 수식이 위와 같이 변경되는 것을 알려준다.
Min-Heap이라는 개념도 추가적으로 설명하며 이는 subtree와 비슷한 개념이다.
d-ary Heap이라는 개념을 통해 이제까지의 Heap에 대해 일반화가 가능해짐을 명시하면서 특징들을 말한다. 우선 각 노드는 최대 d개의 자식 노드를 가질 수 있고, 높이는 logdn이 된다. 그리고 SiftDown의 복잡도가 SiftUp보다 큰 이유는 온전한 트리를 완성하기 위해 어느쪽으로 내려갈지 비교해야하기 때문이다.
마무리로 Summary를 보여주면서 정리한다.
댓글
댓글 쓰기