힙정렬(heap sorting)로 다음 데이터를 내림차순으로 정렬할 때… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 07년 1회차
힙정렬(heap sorting)로 다음 데이터를 내림차순으로 정렬할 때 만들어지는 최초의 힙구조는?7, 1, 15, 13, 19
1
2
3
4
해설
최초의 힙은 루트 19 아래 왼쪽에 13(자식 7·1), 오른쪽에 15가 오는 최대 힙이다.
7, 1, 15, 13, 19를 완전이진트리로 배치한 뒤 마지막 비단말 노드부터 위로 heapify한다. 1은 자식 13·19 중 큰 19와 교환되고, 루트 7은 19와 교환된 뒤 다시 자식 13과 교환되어 배열 [19, 13, 15, 7, 1]이 된다. 이후 최댓값부터 차례로 꺼내면 내림차순으로 정렬된다.
- 루트가 1인 트리는 작은 값이 위로 오는 최소 힙 형태라 이 정렬의 최초 힙이 아니다.
- 루트 13 아래 왼쪽 7(자식 1), 오른쪽 15(자식 19)인 트리는 이진 탐색 트리 형태로, 부모가 자식보다 작은 곳이 있어 힙이 아니다.
- 루트 7 아래 왼쪽 1, 오른쪽 15(자식 13·19)인 트리도 이진 탐색 트리 형태이며 완전이진트리 조건과 힙 조건을 모두 어긴다.
오류나 개정된 내용이 보이면 알려주세요



