4주차_실습과제+해설_힙과 힙정렬(2)

[문제 핵심] :

"제자리 힙 정렬"의 원리는 내가 이해해본 봐로 해보면,

①. n개만큼 삽입된 배열을 rBuildHeap()와 downHeap()함수를 이용해 최대합 정렬로 이진트리를 만든다.

②. ①에서 만든 배열에서 Root노드값과 맨 마지막 자식 노드값을 교환한뒤 다시 최대합 정렬

③. ②의 과정을 뒤에서부터 Root노드의 다음 노드 까지 반복한다.

해설 :

3주차_문제해서 구현한 코드와 같지만, 제자리 힙 정렬 함수[inPlaceHeapSort()]와 비슷하지만, 차이가 있으므로, 잘 비교해야 한다.

해설 :

3주차의 [문제2]와 구현한 방법과 같다.

코드 해설 :

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_1) 유효원소개수 입력

4_2) 노드값 입력

4_3) rBuildHeap()으로 모든 노드값 최대합 이진트리로 재배치

4_4) inPlaceHeapSort()으로 제자리 힙 정렬

코잼민의 코딩이야기