[Competitive Programming] – 연습문제 2장 <작성중>

2.3.8)

최대 힙에서 두 번째로 제일 큰 수가 루트의 자식이 아니라면, 루트와 해당 노드의 거리는 최소 2이며, 경로 내에 최소 하나의 다른 노드가 있다. 최대 힙의 성질에 따라 이 노드는 2번째보다 큰 수이므로 가정에 모순으로 두 번째로 제일 큰 수는 반드시 루트의 자식이다. 세 번째로 큰 수의 경우는 두 번째로 큰 노드가 루트의 왼쪽 자식인 경우 그 노드의 왼쪽 자식인 경우이면 루트의 오른쪽 자식보다 크더라도 최대 힙의 성질을 만족하므로 반드시 루트의 자식일 필요가 없다. 세 번째로 큰 수의 경우 가능한 경우는 루트의 자식이거나, 루트의 자식의 자식인 경우 뿐이다.

2.3.9)

최대 힙을 사용하는 경우는 O(n)의 시간이 든다. 최소 힙을 사용하는 경우는 재귀적 탐색 중 v보다 큰 값의 노드부터는 탐색할 필요가 없지만 최악의 경우는 결국 O(n)이다.

2.3.10)

n을 k개 단위로 나누어 정렬을 할 때 시간 복잡도는 O(n log k)이다. 이후 각 (n / k)개의 부분에서 최솟값을 뽑아내는 것은 O(n / k)이고, 이것을 k개 반복하면 O(n / k * k) = O(n)이다.

따라서 시간복잡도는 O(n + n log k)가 된다.

2.3.11)