Page 255 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

06-8 힙 정렬

선택 정렬을 응용한 알고리즘인 힙 정렬(heap sort)은 힙(heap)의 특성을 이용하여 정렬을 수행
합니다.

힙이란?
힙 정렬은 힙을 사용하여 정렬하는 알고리즘입니다. 힙은 ‘부모의 값이 자식의 값보다 항상

크다’는 조건을 만족하는 완전이진트리입니다. 이때 부모의 값이 자식보다 항상 작아도 힙이
라고 합니다(부모와 자식 요소의 관계만 일정하면 됩니다).
원래 힙은 ‘쌓아 놓음’ 또는 ‘쌓아 놓은 더미’라는 뜻의 단어입니다. 만약 힙 정렬이 어렵거나 트리에 대해 잘 모르겠다면
10장을 먼저 읽은 다음에 다시 이 부분을 공부하면 됩니다.

그림 6-33의 a 는 힙이 아닌 완전이진트리입니다. a 를 힙으로 만들면 b 와 같은 상태가 됩
니다. 부모와 자식 관계는 항상 ‘부모의 값 ≧ 자식의 값’입니다. 따라서 힙의 가장 위쪽에 있

는 루트가 가장 큰 값이 됩니다.

조금만 더! 트리에 대해 알고 싶어요!

10장에서 트리에 대해 설명하겠지만 여기에서 트리에 대해 간단히 알아보겠습니다. 트리의 가장 윗부분을
루트(root)라고 합니다. 그리고 요소의 상하 관계를 ‘부모(parent)’와 ‘자식(child)’이라고 합니다. 그리고
자식 간의 관계는 ‘형제(sibling)’라고 합니다.

완전이진트리란 트리의 한 종류를 말합니다. 사람도 유전적인 특징에 의해 분류하는 것처럼 트리의 종류도
여러 가지입니다. 완전이진트리의 특징은 ‘완전이진’ 상태라는 것입니다. 여기서 ‘완전’이라는 말은 부모
는 자식을 왼쪽부터 추가하는 모양을 유지하라는 뜻입니다. 그리고 ‘이진’이라는 말은 ‘부모가 가질 수 있
는 자식의 개수는 최대 2개다’라는 의미입니다.

06•정렬 255