최대힙(max heap)으로 우선순위큐를 구현하려 한다. 우선순위를 나… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 07년 1회차
최대힙(max heap)으로 우선순위큐를 구현하려 한다. 우선순위를 나타내는 9개의 데이터가 큐에 다음과 같은 순서대로 삽입되었다. 1개의 데이터가 큐에서 삭제된 후, 재 정렬된 힙에서 가장 마지막 원소는 무엇인가? (단, 숫자가 클수록 우선순위가 높다고 가정한다)24, 17, 29, 22, 20, 31, 27, 18, 21
1
17
2
18
3
20
4
21
해설
삭제 후 재정렬된 힙의 마지막 원소는 17이다.
9개를 차례로 삽입하며 부모보다 크면 위로 올리면 힙 배열은 [31, 22, 29, 21, 20, 24, 27, 17, 18]이 된다.
루트 31을 삭제하고 마지막 원소 18을 루트로 옮긴 뒤 아래로 내리면 29, 27과 차례로 자리를 바꿔 [29, 22, 27, 21, 20, 24, 18, 17]이 된다. 따라서 마지막 자리는 17이다.
오류나 개정된 내용이 보이면 알려주세요