[알고리즘] 히프 정렬(Heap sort)

히프정렬이란?

• 히프는 우선 순위 큐를 완전 이진 트리로 구현하는 방법으로 히프는 최대 값이나 최소 값을 쉽게 추출할 수 있는 자료구조이다.
• 최소 히프의 부모 노드 값은 자식 노드의 값 보다 작다.
• 이런 최소 히프의 특성을 이용하여 정렬을 하는 것이다.

 

히프정렬 수행 방법

• 최소히프를 이용하는 방법과 최대히프를 이용하는 방법 총 2가지가 있다.

최대히프를 이용한 수행 방법

1. 정렬할 원소들을 입력하여 최대 히프로 구성한다.
2. 최상단 노드를 배열의 마지막 자리에 배치하고 삭제한다.
3. 나머지 원소에 대해 다시 최대 히프로 재구성한다.
4. 원소의 개수 만큼 위 과정을 반복 수행한다.

 

히프정렬 수행 과정

{25, 1, 24, 20, 7, 2, 8, 18} 의 자료를 히프 정렬을 수행해보자.

 

1. 정렬할 8개의 원소를 완전 이진 트리로 만들고, 최대 히프로 구성한다.

 

 

2. 히프 삭제 연산을 수행하여 최상단 노드 원소 25를 배열의 마지막 자리에 저장하고, 나머지 원소들로 최대 히프를 구성한다.

-

25

 

 

 

3. 2번 과정을 비어있는 트리가 될 때까지 반복한다. 

 

한 단계만 더 해보도록 하자.

 

최상단 노드인 24를 비어있는 노드의 마지막 자리에 저장하고, 나머지 원소들로 최대 히프를 다시 구성한다.

-

24

25

 

 

위 과정을 트리에 아무것도 없어질 때까지 실행하면 배열안에는 정렬된 원소들이 남게 된다.

 

 

히프정렬 복잡도 분석

• 메모리 사용 공간
  • 원소 n개에 대해 n개의 메모리 사용
  • 크기 n의 히프 저장 공간
• 연산 시간
  • n개의 노드에 대해서 완전 이진 트리는  log2 n의 레벨을 가지므로, 완전 이진 트리를 히프로 구성하는 평균 시간은 O(log2 n)
• 결과적으로 평균 시간 복잡도는 O(nlog2 n).