[문제 핵심] :
"제자리 힙 정렬"의 원리는 내가 이해해본 봐로 해보면,
①. n개만큼 삽입된 배열을 rBuildHeap()와 downHeap()함수를 이용해 최대합 정렬로 이진트리를 만든다.
②. ①에서 만든 배열에서 Root노드값과 맨 마지막 자식 노드값을 교환한뒤 다시 최대합 정렬
③. ②의 과정을 뒤에서부터 Root노드의 다음 노드 까지 반복한다.
코드 짠 순서대로 설명해보겠습니다.
1_ 임의의 인덱스에서 최대합 이진트리 조건에 맞도록 배치하는 함수 [downHeap(index)] :
해설 :
3주차_문제해서 구현한 코드와 같지만, 제자리 힙 정렬 함수[inPlaceHeapSort()]와 비슷하지만, 차이가 있으므로, 잘 비교해야 한다.
2_ downHeap()과 재귀를 이용하여, 이진트리의 모든 index를 재배치하도록 하는 함수 [rBuildHeap(index)] :
해설 :
3주차의 [문제2]와 구현한 방법과 같다.
3_ 제자리 힙 정렬해주는 함수 [inPlaceHeapSort()] :
코드 해설 :
3_1) 유효 원소 개수인 n을 보관할 sub_n을 변수 선언, n을 대입
3_2) while 을 이용해 인덱스 맨뒤부터 앞을 제자리 힙 정렬을 해줄 과정 구현
①. sub_n을 차감을 시키면서, 2번째가 될때까지 제자리 힙 정렬을 할것이다.
//while(sub_n!=1) {...}
②. sub_n이 한칸씩 줄여가는 동안 downHeap() 과정을 해야한다. (원리 동일)
★저기서 "if (Heap[cur] >= Heap[child]) break;" 부분에서 downHeap()함수 구현부분과 비교해보면, return으로 걸려있는데
그 이유는 downHeap()은 매개변수의 인덱스 하나의 원소만 자기자리가 잘 배치되도록 조정 되기 때문에 잘 되어있으면 return으로 종료하면 된다.
하지만, inPlaceHeapSort()함수는 다른 인덱스들도 같은 과정을 해야하기 때문에 return을 해버리면, 다른 인덱스는 제자리 힙정렬의 과정을 안하고 종료하게 되므로 break으로 처리 해야 한다.
4_ main판 내용
4_1) 유효원소개수 입력
4_2) 노드값 입력
4_3) rBuildHeap()으로 모든 노드값 최대합 이진트리로 재배치
4_4) inPlaceHeapSort()으로 제자리 힙 정렬