8.5 연습 문제¶

8.5.1 개념 확인¶

배열 [9, 7, 8, 3, 5]는 최대 힙을 나타낸다. 여기에 숫자 10을 삽입한다.

참고 답안

추가한 10의 인덱스는 5이고, 부모 인덱스는 \(\lfloor(5-1)/2\rfloor=2\)이므로 부모 노드의 값은 8이다.
10이 8보다 크므로 첫 번째 교환 후에는 [9, 7, 10, 3, 5, 8]이 된다. 10은 부모 9보다도 크므로 두 번째 교환 후에는 [10, 7, 9, 3, 5, 8]이 된다. 10이 루트에 도달했으므로 힙 재정렬을 마친다.
최종 루트 값은 10이며, 총 2번 교환했다.

배열 [1, 4, 3, 7, 6, 2]는 완전 이진 트리를 나타낸다. 최소 힙에서는 모든 부모의 값이 자식의 값보다 작거나 같아야 한다. 인덱스 \(i\)의 왼쪽과 오른쪽 자식 인덱스는 각각 \(2i+1\), \(2i+2\)다.

인덱스 2의 자식 인덱스와 값은 각각 무엇인가?
인덱스 2의 값은 3이다. 이 노드와 자식의 관계가 최소 힙 규칙에 어긋나는가? 그렇다면 어떤 두 원소를 교환해야 하는가?
2번의 판단에 따라, 규칙에 어긋나면 교환 후 배열을 적고 그렇지 않으면 교환할 필요가 없음을 설명하라. 마지막으로 나머지 부모와 자식 관계도 확인하라.

참고 답안

인덱스 2의 왼쪽 자식 인덱스는 5이고 값은 2다. 오른쪽 자식 인덱스는 6이지만 배열 길이가 6이므로 오른쪽 자식은 없다.
부모의 값 3이 자식의 값 2보다 크므로 최소 힙 규칙에 어긋난다. 인덱스 2와 5의 원소를 교환해야 한다.
교환 후 배열은 [1, 4, 2, 7, 6, 3]이다. 관계를 하나씩 확인하면 1 ≤ 4, 1 ≤ 2, 4 ≤ 7, 4 ≤ 6, 2 ≤ 3이다. 모든 부모의 값이 자식의 값보다 작거나 같으므로 최소 힙 규칙을 만족한다.

데이터 스트림 [4, 1, 7, 3, 8]에서 가장 큰 수 3개를 유지하려면 크기가 3을 넘지 않는 최소 힙을 사용할 수 있다.

먼저 앞의 3개 수를 차례대로 최소 힙에 넣는다. 힙이 가득 찬 뒤에는 새 수를 읽을 때마다 루트보다 크면 루트를 삭제하고 새 수를 넣는다. 그렇지 않으면 힙을 그대로 둔다.

각 수를 읽은 뒤 힙에 남아 있는 수와 루트 값을 적어 보자. 남아 있는 수는 집합으로만 적으면 되며, 힙 배열에서의 순서는 적지 않아도 된다.

참고 답안

각 수를 읽은 뒤의 결과는 다음과 같다.

힙이 가득 차면 루트는 현재 남아 있는 수 중 가장 작은 수다. 새 수가 루트보다 클 때만 새 수로 루트를 대체한다. 최종적으로 남은 {4, 7, 8}이 바로 가장 큰 수 3개다.

정수 배열 nums와 정수 \(k\)가 주어진다. 여기서 \(1 \le k \le n\)이며 \(n\)은 배열 길이다. 배열을 큰 것부터 나열했을 때 \(k\)번째 위치의 원소를 반환하라.

중복 원소도 각각 센다. 예를 들어 [5, 5, 2]에서 두 번째로 큰 원소 역시 5다. 크기가 \(k\)를 넘지 않는 최소 힙을 사용하여 해결하라.

풀이 힌트