힙 정렬

날짜=2024-05-17 공간복잡도 = O(1) **힙 정렬**(heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다. 힙 정렬은 1964년 J. W. J. 윌리엄스에 의해 발명되었다.1964 이 발명 연도는 윌리엄스가 유용한 자료 구조로서 이미 제시한 힙의 탄생일이기도 하다.page=209 같은 해, R. W. 플로이드는 제자리 정렬을 할 수 있는 개선판을 출판하였으며 이는 윌리엄스의 초기 연구를 트리정렬 알고리즘으로 이어나가게 한 것이다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.
# 알고리즘
# n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다. # 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다. # 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다. # 2와 3을 반복한다.
## 시간복잡도
이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어지므로 O(\log n)의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과 n개의 데이터 삭제 및 재구성 시간을 포함한다. 시간 복잡도는 = (\log n+\log(n-1)+...+log 2) = (\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 && right >= k) break; p = cur; if (left = 0; i--){ downheap(i,n); } //for(i=0;i 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 1 && element[locmark/2] > element[locmark]) { swap(locmark/2, locmark); locmark /= 2; } } public void downheap() { int locmark = 1; while(locmark * 2 = 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 }가 있다고 하면 정렬 예시는 다음과 같다. {| class="wikitable" |+ | 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" |+ | 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 |}
# 참고 자료
*