힙 정렬

힙 정렬

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

힙 정렬(Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.

알고리즘

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

 1 void downheap(int cur, int k)
 2 {
 3   int left, right, p;
 4     while(cur < k) {
 5       left = cur * 2 + 1;
 6       right = cur * 2 + 2;and t
 7 
 8       if (left >= k && right >= k) break;
 9 
10       p = cur;
11       if (left < k && data[p] < data[left]) {
12         p = left;
13       }
14       if (right < k && data[p] < data[right]) {
15         p = right;
16       }
17       if (p == cur) break;
18 
19       swap(&data[cur],&data[p]);
20       cur=p;
21     }
22 }
23 
24 void heapify(int n)
25 {
26   int i,p;
27   for(i = (n-1)/2; i >= 0; i--){
28     downheap(i,n);
29   }
30   //for(i=0;i<size;++i)printf("%d ",data[i]);
31   //printf("\n");
32 }
33 
34 void heap()
35 {
36   int k;
37   heapify(size);
38   for(k = size-1; k > 0; ){
39     swap(&data[0],&data[k]);
40     //k--;
41     downheap(0,k);
42     k--;
43   }
44 }

Java

 1 public class Heap
 2 {
 3 	private int[] element; //element[0] contains length
 4 	private static final int ROOTLOC = 1;
 5 	private static final int DEFAULT = 10;
 6 
 7 	public Heap(int size) {
 8 		if(size>DEFAULT) {element = new int[size+1]; element[0] = 0;}
 9 		else {element = new int[DEFAULT+1]; element[0] = 0;}
10 	}
11 
12 	public void add(int newnum) {
13 
14 		if(element.length <= element[0] + 1) {
15 			int[] elementTemp = new int[element[0]*2];
16 			for(int x = 0; x < element[0]; x++) {
17 				elementTemp[x] = element[x];
18 			}
19 			element = elementTemp;
20 		}
21 		element[++element[0]] = newnum;
22 		upheap();
23 	}
24 
25 	public int extractRoot() {
26 		int extracted = element[1];
27 		element[1] = element[element[0]--];
28 		downheap();
29 		return extracted;
30 	}
31 
32 	public void upheap() {
33 		int locmark = element[0];
34 		while(locmark >= 1 && element[locmark/2] > element[locmark]) {
35 			swap(locmark/2, locmark);
36 			locmark /= 2;
37 		}
38 	}
39 
40 	public void downheap() {
41 		int locmark = 1;
42 		while(locmark * 2 <= element[0])
43 		{
44 			if(locmark * 2 + 1 <= element[0]) {
45 				int small = smaller(locmark*2, locmark*2+1);
46 				swap(locmark,small);
47 				locmark = small;
48 			}
49 			else {
50 				swap(locmark, locmark * 2);
51 				locmark *= 2;
52 			}
53 		}
54 	}
55 
56 	public void swap(int a, int b) {
57 		int temp = element[a];
58 		element[a] = element[b];
59 		element[b] = temp;
60 	}
61 
62 	public int smaller(int a, int b) {
63 		return element[a] < element[b] ? a : b;
64 	}
65 }