7.6 힙정렬

힙정렬은 $O(n\ lg\ n)$ 알고리즘임.

7.6.1 힙 구조와 기본적인 힙 연산 루틴

• 트리에서 마디의 깊이: 뿌리마디에서 그 마디로 가는 유일한 경로상에 있는 이음선의 개수
• 트리의 깊이 d: 트리에 속하는 모든 마디의 깊이 중의 최대치
• 트리의 잎: 자식마디가 없는 마디

트리에서 내부마디는 최소한 하나의 자식마디가 있음

→ 즉, 잎이 아닌 마디는 모두 내부마디임. 완전한 이진트리는 다음 조건을 만족하는 이진트리임

• 내부마디는 모두 자식마디가 두 개 있음
• 잎은 모두 깊이가 d 임

완전한 이진트리

힙

본질적으로 완전한 이진트리는 다음 조건을 만족하는 이진트리임

• d-1의 깊이까지는 완전한 이진트리
• 깊이가 d인 마디는 모두 왼쪽 끝으로 모여 있음