Loading AI tools
위키백과, 무료 백과사전
힙 정렬(heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.
이 문서는 참고 문헌 목록을 포함하고 있으나, 각주가 불충분하거나 존재하지 않아 출처가 모호합니다. |
힙 정렬은 1964년 J. W. J. 윌리엄스에 의해 발명되었다.[1] 이 발명 연도는 윌리엄스가 유용한 자료 구조로서 이미 제시한 힙의 탄생일이기도 하다.[2] 같은 해, R. W. 플로이드는 제자리 정렬을 할 수 있는 개선판을 출판하였으며 이는 윌리엄스의 초기 연구를 트리정렬 알고리즘으로 이어나가게 한 것이다.[2]
최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.
이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어지므로 의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과 개의 데이터 삭제 및 재구성 시간을 포함한다.
시간 복잡도는
따라서 힙 정렬은 일반적인 경우 의 시간복잡도를 가진다.
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 }가 있다고 하면 정렬 예시는 다음과 같다.
힙 | 새로 추가된 요소 | 요소 교체 |
---|---|---|
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 |
힙 | 요소 교체 | 요소 삭제 | 요소 정렬 |
---|---|---|---|
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 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.