힙정렬의 오름차순 / 내림차순에 관한 질문

[kde0419]

07년도 기출문제를 풀면서 느꼈고 이전 기출들 몇몇을 보면서도 들던 헷갈리는 포인트라 질문드립니다.

늘 힙정렬을 할시 오름차순 / 내림차순에 대한 최대힙 or 최소힙에 대해서 약간의 혼란이 와서 질문을 남겨드립니다.

최대힙을 기준으로 힙 정렬을 할시, root의 값과 마지막 값을 바꾸고, 그시점에서 다시 힙 원리에 따라 다시 힙을 구성하는걸로 이해하고 있었습니다.

예를들면 이문제서 제가 이해한대로면

좌측(힙) | 우측(정렬된배열)

1 pass 19 13 15 7 1 |

2 pass 15 13 1 7 | 19

3 pass 13 7 1 | 15 19

4 pass 7 1 | 13 15 19

이후 |1 7 13 15 19 (정렬완료)

최대힙을 사용하면 최댓값이 배열의 뒤쪽으로 이동되므로 결과 배열은 오름차순

그래서 저는 최소힙을 해야 내림차순으로 정렬이 되겠다고 판단하여 1번으로 체크하였으나,

실제로는 3번 최대힙 기준을 할때가 정답이였습니다. 물론 최대힙으로 하더라도, 제거되는 원소들을 새로운 배열에 쌓아올린다면 내림차순 이라고 할순 있겠으나, 이것이 힙정렬의 원리는 아닌거같아서, 제가 착각중인 부분을 정확히 모르겠어서 질문 남깁니다.

[홍재연]

질문한 내용에 대해서는 자료구조 이론 교재에 상세하게 적어 두었습니다.

[홍재연]

핵심 내용을 적어보면

최대힙 : 오름차순
최소힙 : 내림차순

본인이 알고 있고, 위에 본인이 적은 것입니다.

[kde0419]

답변 감사합니다!

[홍재연]

그런데
내림차순정렬을 최대힙을 이용하는 것으로 출제된 적이 1번 있었습니다.

이렇게 출제한 사람이 대학교수아닌가요?
이런 사람에게 전산 공부한 사람은 어떻게 될까? 걱정스러울 뿐입니다.

이런 사람은 즉시 교수 해고해야 합니다.