검색어 입력폼
평가점수B

min heap 정렬

등록일 2003.11.23 한글파일한글 (hwp) | 8페이지 | 가격 700원

목차

Ⅰ. 문제
Ⅱ. 입출력의 예
Ⅲ. 알고리즘
Ⅳ. Program Source
Ⅴ. 수행 결과

본문내용

Ⅲ. 알고리즘
우선 정렬하고자 하는 리스트를 주어진 파일에서 읽어와서 list라는 double형 배열에 대입하고 정렬시작하기 전에 time 변수 사용하여 시작 시간을 쟀다.
그리고 정렬하고자 하는 리스트를 하나의 최소 힙(min heap) 구조로 만드는 작업부터 수행하였다. min heap을 구성하기 위하여 함수 adjust를 이용하였는데, 이 함수는 이진트리에 대하여 왼쪽 부트리와 오른쪽 부트리가 min heap일 때, 전체 이진 트리의 root가 min heap이 되도록 조정하였다.(즉, root가 가장 작은 최소값이 되도록 하였다.) 이렇게 하기 위하여 n번 째 노드부터 거꾸로 거슬러 올라가면서 반복적으로 adjust 함수를 호출하였다. 그러나 맨 마지막, 자식이 없는 노드는 그 자체가 min heap이므로 처음으로 자식이 있는 n/2번째 노드부터 첫 번째 노드까지 순서대로 adjust 함수를 호출하였다. 이렇게 하여 min heap에 해당하는 리스트 구조가 되는데 첫 번째 자리에 root가 오고 두 번째 세 번째 자리에는 root의 왼쪽 자식 노드와 root의 오른쪽 자식 노드가 각각 들어가게 된다.
그리고 나서 heap sort를 시작하였다.

참고 자료

C언어에 의한 자료구조론
다운로드 맨위로