힙 정렬

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
힙 정렬
Sorting heapsort anim.gif
분류 정렬 알고리즘
자료 구조 배열
최악 시간복잡도
최선 시간복잡도
평균 시간복잡도
공간복잡도

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

알고리즘[편집]

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

시간복잡도[편집]

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

따라서 힙 정렬은 일반적인 경우 의 시간복잡도를 가진다.

소스 코드[편집]

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   }
43 }

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 }