힙 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{각주 부족|날짜=2024-05-17}}
{{알고리즘 정보
|분류 = [[정렬 알고리즘]]
|그림 = Sorting heapsort anim.gif
|자료구조 = [[배열]]
|최선 = <math>O(n\log n)</math>
|평균 = <math>O(n\log n)</math>
|최악 = <math>O(n\log n)</math>
|공간복잡도 = <math>O(1)</math>
}}

'''힙 정렬'''(heapsort)이란 최대 [[힙 (자료 구조)|힙]] 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.

힙 정렬은 1964년 [[J. W. J. 윌리엄스]]에 의해 발명되었다.<ref>{{harvnb|Williams|1964}}</ref> 이 발명 연도는 윌리엄스가 유용한 자료 구조로서 이미 제시한 힙의 탄생일이기도 하다.<ref name="brass">{{서적 인용|first=Peter |last=Brass |title=Advanced Data Structures |url=https://archive.org/details/advanceddatastru00bras_251 |publisher=Cambridge University Press |year=2008 |isbn=978-0-521-88037-4 |page=[https://archive.org/details/advanceddatastru00bras_251/page/n219 209]}}</ref> 같은 해, [[로버트 플로이드|R. W. 플로이드]]는 제자리 정렬을 할 수 있는 개선판을 출판하였으며 이는 윌리엄스의 초기 연구를 [[트리정렬]] 알고리즘으로 이어나가게 한 것이다.<ref name="brass"/>

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

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

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

시간 복잡도는

<math> = (\log n+\log(n-1)+...+log 2) </math>

<math> = (\log n+\log(n-1)+...+\log 2)+(\log n+\log(n-1)+...+\log 2) </math>

<math> = (n\log n) </math>

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

== 소스 코드 ==
=== [[C++|C]] ===
<syntaxhighlight lang="c" line="1">
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--;
  }
}
</syntaxhighlight>

=== [[자바 (프로그래밍 언어)|자바]] ===
<syntaxhighlight lang="java" line="1">
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;
	}
}
</syntaxhighlight>

== 예시 ==
[[파일:Heapsort-example.gif|350px|섬네일|오른쪽|힙 정렬의 예시.]]
가장 작은 것부터 가장 큰 것까지 정렬하고 싶은 리스트 { 6, 5, 3, 1, 8, 7, 2, 4 }가 있다고 하면 정렬 예시는 다음과 같다.

{| class="wikitable"
|+ style="text-align: left;" | 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 ||   ||  
|}

{| class="wikitable"
|+ style="text-align: left;" | 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 ||   || style="text-align: right;" | 8
|-
| 7, 6, '''1''', 4, 5, '''3''', 2 || 1, 3 ||   || style="text-align: right;" | 8
|-
| '''7''', 6, 3, 4, 5, 1, '''2''' || 7, 2 ||   || style="text-align: right;" | 8
|-
| 2, 6, 3, 4, 5, 1, '''7'''       ||      || 7 || style="text-align: right;" | 8
|-
| '''2''', '''6''', 3, 4, 5, 1 || 2, 6 ||   || style="text-align: right;" | 7, 8
|-
| 6, '''2''', 3, 4, '''5''', 1 || 2, 5 ||   || style="text-align: right;" | 7, 8
|-
| '''6''', 5, 3, 4, 2, '''1''' || 6, 1 ||   || style="text-align: right;" | 7, 8
|-
| 1, 5, 3, 4, 2, '''6'''          ||   || 6 || style="text-align: right;" | 7, 8
|-
| '''1''', '''5''', 3, 4, 2 || 1, 5 ||   || style="text-align: right;" | 6, 7, 8
|-
| 5, '''1''', 3, '''4''', 2 || 1, 4 ||   || style="text-align: right;" | 6, 7, 8
|-
| '''5''', 4, 3, 1, '''2''' || 5, 2 ||   || style="text-align: right;" | 6, 7, 8
|-
| 2, 4, 3, 1, '''5''' ||            || 5 || style="text-align: right;" | 6, 7, 8
|-
| '''2''', '''4''', 3, 1 || 2, 4 ||   || style="text-align: right;" | 5, 6, 7, 8
|-
| '''4''', 2, 3, '''1''' || 4, 1 ||   || style="text-align: right;" | 5, 6, 7, 8
|-
| 1, 2, 3, '''4'''          ||   || 4 || style="text-align: right;" | 5, 6, 7, 8
|-
| '''1''', 2, '''3''' || 1, 3 ||   || style="text-align: right;" | 4, 5, 6, 7, 8
|-
| '''3''', 2, '''1''' || 3, 1 ||   || style="text-align: right;" | 4, 5, 6, 7, 8
|-
| 1, 2, '''3'''          ||   || 3 || style="text-align: right;" | 4, 5, 6, 7, 8
|-
| '''1''', '''2''' || 1, 2 ||   || style="text-align: right;" | 3, 4, 5, 6, 7, 8
|-
| '''2''', '''1''' || 2, 1 ||   || style="text-align: right;" | 3, 4, 5, 6, 7, 8
|-
| 1, '''2''' ||   || 2 || style="text-align: right;" | 3, 4, 5, 6, 7, 8
|-
| '''1''' ||   || 1 || style="text-align: right;" | 2, 3, 4, 5, 6, 7, 8
|-
|      ||   ||   || style="text-align: right;" | 1, 2, 3, 4, 5, 6, 7, 8
|}

== 참고 자료 ==
* {{인용|first=J. W. J. |last=Williams |author-link=J. W. J. Williams |title=Algorithm 232 - Heapsort |year=1964 |journal=[[Communications of the ACM]] |volume=7 |issue=6 |pages=347–348 |doi= 10.1145/512274.512284}}

== 각주 ==
{{각주}}

{{정렬 알고리즘}}


[[분류:정렬 알고리즘]]
[[분류:힙]]
[[분류:비교 정렬]]