개념 확인: Heaps and Priority Queues

1. 빈 최소 우선순위 큐에 8, 3, 11, 5를 넣은 뒤 최솟값 꺼내기를 두 번 할 때 반환값을 적는다.
2. 같은 순서로 일반 큐에 넣고 두 번 꺼내면 반환값이 어떻게 되는지 적고 차이를 설명한다.
3. 정렬 안 한 배열, 정렬된 배열(최솟값을 끝에 둠), 힙으로 구현할 때 넣기와 최솟값 꺼내기의 비용을 적는다.
4. Python heapq에서 넣기, 최솟값 보기, 최솟값 꺼내기에 쓰는 이름을 적는다.

배열은 레벨 순서로 담은 이진트리다.

1. A = [2, 5, 3, 9, 6, 4]가 최소 힙인지 판정한다.
2. B = [2, 5, 3, 4, 1, 7]이 최소 힙인지 판정하고 어기는 부모와 자식을 적는다.
3. 루트의 왼쪽 자식 자리가 비고 오른쪽 자식만 있는 트리가 힙이 될 수 없는 이유를 적는다.
4. A에서 두 번째로 작은 값이 어디에 있는지 적고, 세 번째로 작은 값은 왜 바로 알 수 없는지 적는다.

0부터 세는 최소 힙 배열 a = [1, 4, 2, 8, 5, 7, 3, 9]다.

1. 인덱스 3의 왼쪽·오른쪽 자식 인덱스와 값을 적는다(없으면 없음).
2. 인덱스 6의 부모 인덱스와 값을 적는다.
3. 단말 노드가 놓인 인덱스 범위와 그 값들을 적는다.
4. 1부터 세는 자료라면 인덱스 i의 두 자식과 부모 식이 어떻게 되는지 적는다.

1. 레벨 3까지 가득 찬 완전 이진트리의 노드 수를 적는다.
2. 노드 수 n = 20, 100, 1,000인 완전 이진트리의 높이를 적는다.
3. n = 31과 n = 32의 높이를 적고 차이가 생기는 이유를 적는다.
4. 힙의 넣기와 최솟값 꺼내기가 O(log n)인 이유를 높이로 설명한다.

다음 문장이 맞는지 판단하고 틀리면 고친다.

1. 최소 힙을 중위 순회하면 값이 오름차순으로 나온다.
2. 최소 힙의 부등호를 뒤집으면 루트에 최댓값이 오는 최대 힙이 된다.
3. BST에서는 루트에 항상 최솟값이 온다.
4. 힙이 노드 기반 BST보다 부모를 찾기 쉬운 이유는 배열 인덱스 계산 때문이다.