다음과 같은 키 값을 가지는 원소들을 공백 힙(empty heap)에 … | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
다음과 같은 키 값을 가지는 원소들을 공백 힙(empty heap)에 차례대로 삽입하여 최대 힙(max heap)을 생성한 다음, 삭제 연산을 한 번 수행한 후의 결과는?
4, 16, 57, 9, 32, 45, 20, 19
1
2
3
4
해설

삭제 후의 최대 힙은 레벨 순서로 45 / 32, 20 / 19, 9, 16, 4이다.

차례로 삽입하며 부모와 교환(up-heap)하면 힙 배열은 57, 32, 45, 19, 9, 16, 20, 4가 된다. 삭제는 루트 57을 꺼내고 마지막 원소 4를 루트로 올린 뒤, 더 큰 자식과 교환하며 내려간다(4↔45, 4↔20).

그 결과 배열은 45, 32, 20, 19, 9, 16, 4가 된다.

  • 루트가 57이고 오른쪽 자식이 45인 트리: 마지막 원소 4만 빠진 형태로, 루트(최댓값)를 꺼내는 힙 삭제가 반영되지 않았다.
  • 루트가 57이고 오른쪽 자식이 20인 트리: 최댓값 57이 아니라 45가 삭제된 형태이다.
  • 20의 자식이 4, 16 순서인 트리: 4는 마지막 위치에서 내려온 원소이므로 20의 오른쪽 자식이어야 하고, 왼쪽 자식은 16이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 08년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기