한국어
메뉴

자료 구조와 알고리즘

부모의 값이 자식의 값 이상이 되는 최대 힙을, 루트를 a[0]으로 하는 배열로 나타내고 있다. 힙 50, 30, 40, 10, 20, 35에 45를 추가한다. 맨 끝에 놓은 뒤 부모보다 큰 동안은 부모와 교환하는 조작을 수행한 후의 배열은?

  1. A50, 30, 40, 10, 20, 35, 45
  2. B45, 30, 50, 10, 20, 35, 40
  3. C50, 30, 45, 10, 20, 35, 40
정답과 해설 보기

정답: C. 50, 30, 45, 10, 20, 35, 40

45는 a[6]에 놓이며, 부모는 a[(6−1)÷2] = a[2] = 40입니다. 45 > 40이므로 교환하여 a[2]로 옮겨 갑니다. 다음 부모 a[0] = 50은 45보다 크므로 여기서 멈추고, 50, 30, 45, 10, 20, 35, 40이 됩니다. 교환은 트리의 높이만큼만 일어나므로 추가는 O(log n)이고, 최댓값 꺼내기도 마찬가지로 O(log n)입니다. 이 성질 때문에 이진 힙은 우선순위 큐의 구현에 자주 쓰입니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 이진 탐색 트리를 중위 순회(왼쪽 서브트리, 그 노드, 오른쪽 서브트리 순으로 방문한다)로 따라갔을 때, 방문한 노드의 값은 어떻게 늘어서는가? 값은 모두 서로 다르다고 한다.
  2. 빈 이진 탐색 트리에 50, 30, 70, 20, 40, 60, 80의 순서로 값을 삽입했다. 이 트리를 후위 순회(왼쪽 서브트리, 오른쪽 서브트리, 그 노드 순으로 방문한다)로 따라갔을 때의 순서는?
  3. 빈 이진 탐색 트리에 1, 2, 3, …, 1000의 순서로 값을 삽입했다(균형을 잡는 조작은 하지 않는다). 이 트리에서 1000을 찾을 때, 루트부터 비교하기 시작하여 찾을 때까지 비교하는 노드의 수는?
  4. 데이터베이스나 파일 시스템의 인덱스에 이진 탐색 트리가 아니라 B 트리(B+ 트리 포함)가 자주 쓰이는 주된 이유는?
  5. 정점이 100만 개, 간선이 300만 개 정도인 도로망처럼 정점 수에 비해 간선이 적은(희소한) 그래프를 메모리에 저장하는 방법으로 적절한 것은?