힙 정렬

힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.

힙 정렬

분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	$O(n\log n)$
최선 시간복잡도	$O(n\log n)$
평균 시간복잡도	$O(n\log n)$
공간복잡도	$O(1)$

힙 정렬은 1964년 J. W. J. 윌리엄스에 의해 발명되었다. 이 발명 연도는 윌리엄스가 유용한 자료 구조로서 이미 제시한 힙의 탄생일이기도 하다. 같은 해, R. W. 플로이드는 제자리 정렬을 할 수 있는 개선판을 출판하였으며 이는 윌리엄스의 초기 연구를 트리정렬 알고리즘으로 이어나가게 한 것이다.

최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.

알고리즘

1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
4. 2와 3을 반복한다.

시간복잡도

이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어지므로 $O(\log n)$의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과 $n$개의 데이터 삭제 및 재구성 시간을 포함한다.

시간 복잡도는

$=(\log n+\log(n-1)+...+log2)$

$=(\log n+\log(n-1)+...+\log 2)+(\log n+\log(n-1)+...+\log 2)$

$=(n\log n)$

따라서 힙 정렬은 일반적인 경우 $O(n\log n)$의 시간복잡도를 가진다.

소스 코드

C

void downheap(int cur, int k)
{
  int left, right, p;
    while(cur < k) {
      left = cur * 2 + 1;
      right = cur * 2 + 2;

      if (left >= k && right >= k) break;

      p = cur;
      if (left < k && data[p] < data[left]) {
        p = left;
      }
      if (right < k && data[p] < data[right]) {
        p = right;
      }
      if (p == cur) break;

      swap(&data[cur],&data[p]);
      cur=p;
    }
}

void heapify(int n)
{
  int i,p;
  for(i = (n-1)/2; i >= 0; i--){
    downheap(i,n);
  }
  //for(i=0;i<size;++i)printf("%d ",data[i]);
  //printf("\n");
}

void heap()
{
  int k;
  heapify(size);
  for(k = size-1; k > 0; ){
    swap(&data[0],&data[k]);
    //k--;
    downheap(0,k);
    k--;
  }
}

자바

public class Heap
{
	private int[] element; //element[0] contains length
	private static final int ROOTLOC = 1;
	private static final int DEFAULT = 10;

	public Heap(int size) {
		if(size>DEFAULT) {element = new int[size+1]; element[0] = 0;}
		else {element = new int[DEFAULT+1]; element[0] = 0;}
	}

	public void add(int newnum) {

		if(element.length <= element[0] + 1) {
			int[] elementTemp = new int[element[0]*2];
			for(int x = 0; x < element[0]; x++) {
				elementTemp[x] = element[x];
			}
			element = elementTemp;
		}
		element[++element[0]] = newnum;
		upheap();
	}

	public int extractRoot() {
		int extracted = element[1];
		element[1] = element[element[0]--];
		downheap();
		return extracted;
	}

	public void upheap() {
		int locmark = element[0];
		while(locmark > 1 && element[locmark/2] > element[locmark]) {
			swap(locmark/2, locmark);
			locmark /= 2;
		}
	}

	public void downheap() {
		int locmark = 1;
		while(locmark * 2 <= element[0])
		{
			if(locmark * 2 + 1 <= element[0]) {
				int small = smaller(locmark*2, locmark*2+1);
				if(element[small] >= element[locmark]) break;
				swap(locmark,small);
				locmark = small;
			}
			else {
			    if(element[locmark * 2] >= element[locmark]) break;
				swap(locmark, locmark * 2);
				locmark *= 2;
			}
		}
	}

	public void swap(int a, int b) {
		int temp = element[a];
		element[a] = element[b];
		element[b] = temp;
	}

	public int smaller(int a, int b) {
		return element[a] < element[b] ? a : b;
	}
}

예시

힙 정렬의 예시.

가장 작은 것부터 가장 큰 것까지 정렬하고 싶은 리스트 { 6, 5, 3, 1, 8, 7, 2, 4 }가 있다고 하면 정렬 예시는 다음과 같다.

1. 힙 만들기

힙	새로 추가된 요소	요소 교체
null	6
6	5
6, 5	3
6, 5, 3	1
6, 5, 3, 1	8
6, 5, 3, 1, 8		5, 8
6, 8, 3, 1, 5		6, 8
8, 6, 3, 1, 5	7
8, 6, 3, 1, 5, 7		3, 7
8, 6, 7, 1, 5, 3	2
8, 6, 7, 1, 5, 3, 2	4
8, 6, 7, 1, 5, 3, 2, 4		1, 4
8, 6, 7, 4, 5, 3, 2, 1

2. 정렬

힙	요소 교체	요소 삭제	요소 정렬
8, 6, 7, 4, 5, 3, 2, 1	8, 1
1, 6, 7, 4, 5, 3, 2, 8		8
1, 6, 7, 4, 5, 3, 2	1, 7		8
7, 6, 1, 4, 5, 3, 2	1, 3		8
7, 6, 3, 4, 5, 1, 2	7, 2		8
2, 6, 3, 4, 5, 1, 7		7	8
2, 6, 3, 4, 5, 1	2, 6		7, 8
6, 2, 3, 4, 5, 1	2, 5		7, 8
6, 5, 3, 4, 2, 1	6, 1		7, 8
1, 5, 3, 4, 2, 6		6	7, 8
1, 5, 3, 4, 2	1, 5		6, 7, 8
5, 1, 3, 4, 2	1, 4		6, 7, 8
5, 4, 3, 1, 2	5, 2		6, 7, 8
2, 4, 3, 1, 5		5	6, 7, 8
2, 4, 3, 1	2, 4		5, 6, 7, 8
4, 2, 3, 1	4, 1		5, 6, 7, 8
1, 2, 3, 4		4	5, 6, 7, 8
1, 2, 3	1, 3		4, 5, 6, 7, 8
3, 2, 1	3, 1		4, 5, 6, 7, 8
1, 2, 3		3	4, 5, 6, 7, 8
1, 2	1, 2		3, 4, 5, 6, 7, 8
2, 1	2, 1		3, 4, 5, 6, 7, 8
1, 2		2	3, 4, 5, 6, 7, 8
1		1	2, 3, 4, 5, 6, 7, 8
			1, 2, 3, 4, 5, 6, 7, 8

참고 자료

• Williams, J. W. J. (1964), “Algorithm 232 - Heapsort”, 《Communications of the ACM》 7 (6): 347–348, doi:10.1145/512274.512284