6-8. 힙 정렬(Heap Sort)

힙이란?

• 힙(heap)을 사용해 정렬하는 알고리즘
• 힙은 '부모의 값이 자식보다 항상 크다'는 조건을 만족하는 완전이진트리
• 부모의 값이 자식보다 항상 작아도 힙이라고 함(부모와 자식 요소의 관계만 일정하면 됨)

 

 

 

완전이진트리 → 힙

 

 

• 힙은 루트가 가장 큰(혹은 작은) 값이어야 함
• 즉, 모든 부모와 자식의 관계는 항상 부모의 값 >= 자식의 값이 성립되어야 함
• 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않음

 

 

 

힙의 요소를 배열에 저장

 

 

 

부모와 자식의 인덱스 사이에는 다음과 같은 관계 성립

1. 부모는 a[(i - 1) / 2]
2. 왼쪽 자식은 a[i * 2 + 1]
3. 오른쪽 자식은 a[i * 2 + 2]

 

 

 

 

 

힙 정렬

• '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘
• 힙에서 가장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어놓으면 배열의 정렬 종료
• 힙 정렬은 선택 정렬을 응용한 알고리즘이며 힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰 값을 구해야 함

 

 

 

 

 

[실습 코드]