Quiz of Week 3 - Priority queues

Quiz of Week 3 - Priority queues

Priority Queues에 대한 강의를 마치고 바로 간단한 퀴즈를 풀었다.

Quiz라서 통과 기준이 좀 더 낮은 것같다.

1번 문제는 min-heap 특성에 부합하지 않는 edge가 얼마나 있는지 찾는 문제이다.

2번 문제는 13개의 노드가 있고 13개의 서브트리 중 몇개가 온전한지 알아내야 한다.

3번 문제는 온전한 트리를 배열로 주며 이 중 max-heap 특성을 위반하는 edge가 몇개인지 찾는 것이다.

4번 문제는 max-heap이 있으며 10^5개의 원소가 5-ary 트리가 온전히 존재할 때 Insert로 인해 대략 몇번의 비교가 이루어 질지 알아내는 것이다.

5번 문제는 max-heap이 10^6개의 원소가 온전한 7-ary 트리로 존재할 때 ExtractMax는 얼마나 호출하는지 계산하는 것이다.

6번은 d-ary 트리가 1부터 시작하는 배열에 있을 때 i번째 노드의 자식을 암시하는 적합한 식을 찾는 것이다.

우선 1번 문제의 경우 문제에 나와있듯 간단하게 부모 값이 자식값보다 큰 엣지를 찾으면 되는데 4개가 있는 것을 알 수 있다.

2번은 우선 마지막 세대에 해당하는 6개의 노드를 서브트리로 보고 6개가 해당하며 상위 세대로 넘어가면 4개의 서브트리가, 그 위의 세대로 넘어가면 1개가 해당하므로 11개인 것을 알 수 있다.

배열이라고 특별히 다른 것은 없기 때문에 트리를 그려서 부모값이 자식값보다 작은 엣지들을 찾으면 5개가 있음을 알 수 있었다.

여기서부터 사실 헤메기 시작했는데 해설에 있는 내용을 그대로 받아들이기로 했다. Insert 동작의 복잡도가 logdn이므로 해당 값을 모두 입력하면 8에 근사한 값이 나온다.

ExtractMax의 running time 중 최악의 경우는 d logdn 이 되어 50에 근사한 값이 나온다.

이 문제는 대입을 통해 검증만 한 것을 토대로 아닌 보기들을 제외했는데 시간이 날 때 증명을 해봐야겠다.