[출처 : http://shings47.tistory.com/156]
▣ 실행 시간 : nlogn
▣ Sort in Place : 정렬을 위한 고정된 크기의 추가적인 공간이 필요함.
▣ Heap : efficient priority queue 사용 (가장 큰 수(or작은 수)가 root에 위치한다.)
▣ 기본 개념
-Perfect Binary Tree와 Complete Binary Tree에 대한 개념
-Heap은 Complete Binary Tree이면서 부모 노드의 값이 자식 노드의 값보다 큰(Max_Heap의 경우) 조건을 만족
-length[Array] >= heap_size[Array]
▣Heap Computation
부모(i) = return └i/2┘
Left 자식(i) = return 2i
Right 자식(i) = return 2i+1
Heap_Height = └logn┘
▣알고리즘
여기까지는 Heap_Sort에 대해 이해하기 위한 기본 개념이다.
Heap_Sort의 알고리즘을 이해하기 위해서는 Max_Heapify와 Building a Max_Heap 과정을 구현하여야 한다.
▣ 구현 예시
예시1 출처 : http://www.programmersheaven.com/download/34394/0/ZipView.aspx
예시2 출처 : http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Heapsort
▣ Sort in Place : 정렬을 위한 고정된 크기의 추가적인 공간이 필요함.
▣ Heap : efficient priority queue 사용 (가장 큰 수(or작은 수)가 root에 위치한다.)
▣ 기본 개념
-Perfect Binary Tree와 Complete Binary Tree에 대한 개념
-Heap은 Complete Binary Tree이면서 부모 노드의 값이 자식 노드의 값보다 큰(Max_Heap의 경우) 조건을 만족
-length[Array] >= heap_size[Array]
▣Heap Computation
부모(i) = return └i/2┘
Left 자식(i) = return 2i
Right 자식(i) = return 2i+1
Heap_Height = └logn┘
▣알고리즘
여기까지는 Heap_Sort에 대해 이해하기 위한 기본 개념이다.
Heap_Sort의 알고리즘을 이해하기 위해서는 Max_Heapify와 Building a Max_Heap 과정을 구현하여야 한다.
1) Max_Heapify(A, i)
l <- Left(i)
r <- Right(i)
//아래 코드는 부모와 두 자식 노드, 3개 중에서 largest값을 찾는다.
if i <= heap_size[A] and A[l] > A[i]
then largest <- l
else largest <- i
if r <= heap_size[A] and A[r] > A[largest]
then largest <- r
//부모 노드가 제일 큰 값이 아닐경우 l, r 중에 largest로 지정된 값과 교환 후 recursive하게 아래로 진행
if largest != i
then exchange A[i] <-> A[largest]
Max_Heapify(A, largest)
l <- Left(i)
r <- Right(i)
//아래 코드는 부모와 두 자식 노드, 3개 중에서 largest값을 찾는다.
if i <= heap_size[A] and A[l] > A[i]
then largest <- l
else largest <- i
if r <= heap_size[A] and A[r] > A[largest]
then largest <- r
//부모 노드가 제일 큰 값이 아닐경우 l, r 중에 largest로 지정된 값과 교환 후 recursive하게 아래로 진행
if largest != i
then exchange A[i] <-> A[largest]
Max_Heapify(A, largest)
2) Buiding a Max_Heap
heap_size[A] <- length[A]
//└length[A]/2┘ == 마지막 노드의 부모 노드에서부터라는 뜻 Leaf를 제외한 마지막 노드
for i <- └length[A]/2┘ downto 1
do Max_Heapify(A, i)
heap_size[A] <- length[A]
//└length[A]/2┘ == 마지막 노드의 부모 노드에서부터라는 뜻 Leaf를 제외한 마지막 노드
for i <- └length[A]/2┘ downto 1
do Max_Heapify(A, i)
3) Heap_Sort
- 위의 두가지 코드를 이용하여 구현
- 초기에 Max_Heap으로 만든 후 노드값 i와 root노드의 값을 서로 바꾸면서 1에 대해서만 Max_Heapify를 해주게되면 계속해서 Max_Heap의 형태를 유지하게 된다.
Buiding a Max_Heap(A)
for i <- length[A] downto 2
do exchange A[1] <-> A[i]
heapsize[A] <- heapsize[A]-1
Max_Heapify(A, 1)
- 위의 두가지 코드를 이용하여 구현
- 초기에 Max_Heap으로 만든 후 노드값 i와 root노드의 값을 서로 바꾸면서 1에 대해서만 Max_Heapify를 해주게되면 계속해서 Max_Heap의 형태를 유지하게 된다.
Buiding a Max_Heap(A)
for i <- length[A] downto 2
do exchange A[1] <-> A[i]
heapsize[A] <- heapsize[A]-1
Max_Heapify(A, 1)
▣ 구현 예시
예시1 출처 : http://www.programmersheaven.com/download/34394/0/ZipView.aspx
#include<stdio.h>
#define MAX 10
#define LOOP(A,B) for(i=A;i<B;i++)
void heapify( int [] , int );
void heapsort( int [] , int );
void main()
{
int i, list[MAX];
clrscr();
printf("Randomized list is :\n");
LOOP(0,MAX)
list[i]=rand()/100;
LOOP(0,MAX)
printf("%8d",list[i]);
LOOP(0,MAX)
heapify(list,i);
printf("\n\nHeapified list is :\n");
LOOP(0,MAX)
printf("%8d",list[i]);
heapsort(list,MAX-1);
printf("\nSorted list is :\n");
LOOP(0,MAX)
printf("%8d",list[i]);
}
//Convert any random array to heap array
void heapify ( int list[] , int newnode )
{
int done=0, dad, temp;
dad = ( newnode - 1 ) / 2;
while( dad >= 0 && !done)
{
if(list[newnode] > list[dad])
{
temp = list[newnode];
list[newnode]=list[dad];
list[dad]=temp;
newnode = dad;
dad = dad/2;
}
else
done = 1;
}
}
void heapsort ( int list[] , int last )
{
int i,temp;
while(last > 0 )
{
temp = list[0];
list[0]=list[last];
list[last]= temp;
LOOP(0,last)
heapify(list,i);
last--;
}
}
#define MAX 10
#define LOOP(A,B) for(i=A;i<B;i++)
void heapify( int [] , int );
void heapsort( int [] , int );
void main()
{
int i, list[MAX];
clrscr();
printf("Randomized list is :\n");
LOOP(0,MAX)
list[i]=rand()/100;
LOOP(0,MAX)
printf("%8d",list[i]);
LOOP(0,MAX)
heapify(list,i);
printf("\n\nHeapified list is :\n");
LOOP(0,MAX)
printf("%8d",list[i]);
heapsort(list,MAX-1);
printf("\nSorted list is :\n");
LOOP(0,MAX)
printf("%8d",list[i]);
}
//Convert any random array to heap array
void heapify ( int list[] , int newnode )
{
int done=0, dad, temp;
dad = ( newnode - 1 ) / 2;
while( dad >= 0 && !done)
{
if(list[newnode] > list[dad])
{
temp = list[newnode];
list[newnode]=list[dad];
list[dad]=temp;
newnode = dad;
dad = dad/2;
}
else
done = 1;
}
}
void heapsort ( int list[] , int last )
{
int i,temp;
while(last > 0 )
{
temp = list[0];
list[0]=list[last];
list[last]= temp;
LOOP(0,last)
heapify(list,i);
last--;
}
}
예시2 출처 : http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Heapsort
void
heapsort(int arr[], unsigned int N)
{
int t; /* the temporary value */
unsigned int n = N, parent = N/2, index, child; /* heap indexes */
/* loop until array is sorted */
for (;;) {
if (parent > 0) {
/* first stage - Sorting the heap */
t = arr[--parent]; /* save old value to t */
} else {
/* second stage - Extracting elements in-place */
n--; /* make the heap smaller */
if (n == 0) return; /* When the heap is empty, we are done */
t = arr[n]; /* save lost heap entry to temporary */
arr[n] = arr[0]; /* save root entry beyond heap */
}
/* insert operation - pushing t down the heap to replace the parent */
index = parent; /* start at the parent index */
child = index * 2 + 1; /* get its left child index */
while (child < n) {
/* choose the largest child */
if (child + 1 < n && arr[child + 1] > arr[child]) {
child++; /* right child exists and is bigger */
}
/* is the largest child larger than the entry? */
if (arr[child] > t) {
arr[index] = arr[child]; /* overwrite entry with child */
index = child; /* move index to the child */
child = index * 2 + 1; /* get the left child and go around again */
} else {
break; /* t's place is found */
}
}
/* store the temporary value at its new location */
arr[index] = t;
}
}
{
int t; /* the temporary value */
unsigned int n = N, parent = N/2, index, child; /* heap indexes */
/* loop until array is sorted */
for (;;) {
if (parent > 0) {
/* first stage - Sorting the heap */
t = arr[--parent]; /* save old value to t */
} else {
/* second stage - Extracting elements in-place */
n--; /* make the heap smaller */
if (n == 0) return; /* When the heap is empty, we are done */
t = arr[n]; /* save lost heap entry to temporary */
arr[n] = arr[0]; /* save root entry beyond heap */
}
/* insert operation - pushing t down the heap to replace the parent */
index = parent; /* start at the parent index */
child = index * 2 + 1; /* get its left child index */
while (child < n) {
/* choose the largest child */
if (child + 1 < n && arr[child + 1] > arr[child]) {
child++; /* right child exists and is bigger */
}
/* is the largest child larger than the entry? */
if (arr[child] > t) {
arr[index] = arr[child]; /* overwrite entry with child */
index = child; /* move index to the child */
child = index * 2 + 1; /* get the left child and go around again */
} else {
break; /* t's place is found */
}
}
/* store the temporary value at its new location */
arr[index] = t;
}
}
이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록
만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.
■ 힙 정렬 개념
힙(heap)은 우선순위 큐(priority queue)의 일종으로 우선순위가 높은 요소를 효율적으로 관리하는 자료구조
힙은 배열 또는 연결리스트를 이용한 나무구조로 구현
힙은 부가적 메모리를 필요로 하지 않으며 매우 빠른 성능을 갖음
입력 자료에 무관하게 고른 성능을 보임
힙은 n개의 레코드로 구성된 입력 파일을 하나의 최대 힙(max heap) 즉, 각 노드에 저장되어 있는 원소의 값이 서브노드에 저장되어 있는 원소의 값보다 큰 전이진 트리 구조로 만드는 것
레벨 l 에서 노드의 수가 2l-1< n <2l+1 을 만족하여 레벨 l 상에서 모든 노드들은 가능하면 왼쪽의 위치에 존재하게 됨
■ 우선순위 큐(Priority Queue)
어떤 자료 구조를 의미하는 것이 아니라, 다만 스택 또는 큐 등을 이용하여 각각 우선순위를 갖는 자료를 관리하는 추상적인 개념
생성(construct) : N개의 자료로 우선순위 큐를 생성함
생성 = N번의 삽입
삽입(insert) : 우선순위 큐에 새로운 자료를 삽입함
제거(remove) : 가장 높은 우선순위를 갖는 자료를 제거함
대치(replace) : 가장 높은 우선순위를 갖는 자료와 새로운 자료를 바꿈
대치 = 제거 + 삽입
변경(change) : 우선순위 큐 내에 있는 자료의 순위를 변경함
변경 = 삭제 + 삽입
삭제(delete) : 우선순위 큐 내에 있는 임의의 자료를 삭제함
결합(join) : 두개의 우선순위 큐를 결합하여 큰 우선순위 큐를 생성함
■ 힙(Heap)
키 값의 크기로 우선순위를 결정하는 자료구조
힙은 나무구조로 표현되는데, 이때 부모의 키 값은 반드시 두 자식의 키 값보다 작으면 않된다.
루트 노드에는 키 값이 가장 큰 자료가 위치하게 된다.
단말노드에 삽입된 자료는 우선순위를 맞추기 위해 상위 노드와 비교 후 교환되어져야 한다.
― 최단말 노드에 삽입된 자료는 부모와 비교된다.
― 큰 값을 갖는 경우 부모와 교체된다.
― 계속해서 상위에 있는 부모와 비교되고 크면 교체된다.
반대로 가장 큰 값을 갖는 루트 노드를 제거하는 경우
― 먼저 뿌리 노드의 자료를 제거한다.
― 뿌리 노드가 비어 있으므로 최단말 노드(min)의 자료를 임시로 뿌리에 옮긴다.
― 크기가 작은 노드(min)가 루트를 차지하고 있으므로 아래의 두 자식 노드중에서
큰 값을 갖는 자료가 임시 자료(min)와 교체된다.
― 아래 레벨로 밀려난 임시 노드(min)는 또 다시 자식 노드와 비교되고 그중에서
큰 값을 갖는 노드와 교체된다.
― 임시 노드(min)의 자식 노드가 더 작은 값을 갖는 곳 까지 반복 수행된다.
■ 배열로 트리 구현
연결리스트를 이용하면 부모 자식관계를 포인터로 직접 결합 가능
배열을 이용하게되면 첨자를 조작하여 간접적으로 연결해야 함
- 링크를 저장할 공간을 필요로하지 않는 장점을 가짐
- 불균형 트리의 경우 빈 노드를 위해서도 배열 공간을 확보해야 함
- 따라서 균형 트리(balanced tree)에 대해서 배열을 이용한다
힙은 균형 트리이므로 배열을 이용하는 것이 유리함
■ 힙 정렬의 방법
▷ 힙을 생성
- 힙의 크기를 배열의 크기로 하고 BuildHeap을 통해 힙조건에 맞게 수정하는 방식
- 배열에 저장은 초기 자료의 순서대로 힙이라 가정하고 트리로 구성함
― 부모 노드는 항상 두 자식 보다 큰 값을 가짐
- BuildHeap을 통해 하나씩 제자리를 찾아 내려보냄
▷ 제거 동작을 반복 수행
― 가장 큰 값을 갖는 루트에서 제거 동작을 수행하고
― 루트가 없는 힙에서는 최단말 노드가 임시로 루트가 되며 제자리를 찾아 내려가게 됨
― 루트에서 뽑아낸 자료는 임의 배열에 끝에서부터 차례로 저장함
■ 힙 정렬 알고리즘
-------------------------------------------------------------------------------
#define LeftChild(i) (2*(i))
void PercDown (int A[ ], int i, int N) /* BuildHeap 수행*/
{
int Child, Temp; /*Temp는 루트의 값을 보관 */
/*1*/ for(Tmp=A[i]; LeftChild(i)<=N; i=Child)
{
/*2*/ Child=LeftChild(i);
/*3*/ if(Child!=N && A[Child+1] > A[Child])
/*4*/ Child++;
/*5*/ if( Temp<A[Child]) /* 루프를 돌면서 루트의 값이 */
/*6*/ A[i]=A[Child]; /* 자기의 위치로 내려옴 */
else
/*7*/ break;
}
/*8*/ A[i]=Temp;
}
void Heapsort(int A[ ],int N)
{
int i;
/*a*/ for( i = N/2; i > 0; i--) /* BuildHeap 호출*/
/*b*/ PercDown(A, i, N);
/*c*/ for( i = N; i >= 2; i--)
{
/*d*/ Swap(&A[1], &A[i]); /* DeleteMax 루트의 값을 제일 뒤로 */
/*e*/ PercDown(A, 1, i-1); /* 제일 뒤에 있던 값이 루트에서 자기 위치로 */
} /* BuildHeap 호출*/
}
-------------------------------------------------------------------------------
■ 성능
▷ MaxHeap을 만들어서 DeleteMax를 반복 수행하여 정렬
▷ N을 입력 파일의 크기라 하면 BuildHeap O(N), N번 DeleteMax O(NlogN)
▷ BuildHeap은 내부노드(총 N/2개)에서만 수행되면 됨
- 단말노드는더이상내려갈곳이없으므로을적용할필요가없음
- N/2 노드(마지막 내부노드 위치)부터 뿌리 노드까지만 적용되면 됨
- 적용 범위가 반으로 줄었기 때문에 성능면에서 크게 향상된다. O(NlogN)
▷ 이론적으로 이상적인 O(NlogN)이나 실제 수행시간 길다.
▷ 뛰어난 성능을 가지면서도 추가적인 메모리를 필요로 하지 않음
자료 출처 : http://www.dreamy.pe.kr/zbxe/codeclip/5944
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.
■ 힙 정렬 개념
힙(heap)은 우선순위 큐(priority queue)의 일종으로 우선순위가 높은 요소를 효율적으로 관리하는 자료구조
힙은 배열 또는 연결리스트를 이용한 나무구조로 구현
힙은 부가적 메모리를 필요로 하지 않으며 매우 빠른 성능을 갖음
입력 자료에 무관하게 고른 성능을 보임
힙은 n개의 레코드로 구성된 입력 파일을 하나의 최대 힙(max heap) 즉, 각 노드에 저장되어 있는 원소의 값이 서브노드에 저장되어 있는 원소의 값보다 큰 전이진 트리 구조로 만드는 것
레벨 l 에서 노드의 수가 2l-1< n <2l+1 을 만족하여 레벨 l 상에서 모든 노드들은 가능하면 왼쪽의 위치에 존재하게 됨
■ 우선순위 큐(Priority Queue)
어떤 자료 구조를 의미하는 것이 아니라, 다만 스택 또는 큐 등을 이용하여 각각 우선순위를 갖는 자료를 관리하는 추상적인 개념
생성(construct) : N개의 자료로 우선순위 큐를 생성함
생성 = N번의 삽입
삽입(insert) : 우선순위 큐에 새로운 자료를 삽입함
제거(remove) : 가장 높은 우선순위를 갖는 자료를 제거함
대치(replace) : 가장 높은 우선순위를 갖는 자료와 새로운 자료를 바꿈
대치 = 제거 + 삽입
변경(change) : 우선순위 큐 내에 있는 자료의 순위를 변경함
변경 = 삭제 + 삽입
삭제(delete) : 우선순위 큐 내에 있는 임의의 자료를 삭제함
결합(join) : 두개의 우선순위 큐를 결합하여 큰 우선순위 큐를 생성함
■ 힙(Heap)
키 값의 크기로 우선순위를 결정하는 자료구조
힙은 나무구조로 표현되는데, 이때 부모의 키 값은 반드시 두 자식의 키 값보다 작으면 않된다.
루트 노드에는 키 값이 가장 큰 자료가 위치하게 된다.
단말노드에 삽입된 자료는 우선순위를 맞추기 위해 상위 노드와 비교 후 교환되어져야 한다.
― 최단말 노드에 삽입된 자료는 부모와 비교된다.
― 큰 값을 갖는 경우 부모와 교체된다.
― 계속해서 상위에 있는 부모와 비교되고 크면 교체된다.
반대로 가장 큰 값을 갖는 루트 노드를 제거하는 경우
― 먼저 뿌리 노드의 자료를 제거한다.
― 뿌리 노드가 비어 있으므로 최단말 노드(min)의 자료를 임시로 뿌리에 옮긴다.
― 크기가 작은 노드(min)가 루트를 차지하고 있으므로 아래의 두 자식 노드중에서
큰 값을 갖는 자료가 임시 자료(min)와 교체된다.
― 아래 레벨로 밀려난 임시 노드(min)는 또 다시 자식 노드와 비교되고 그중에서
큰 값을 갖는 노드와 교체된다.
― 임시 노드(min)의 자식 노드가 더 작은 값을 갖는 곳 까지 반복 수행된다.
■ 배열로 트리 구현
연결리스트를 이용하면 부모 자식관계를 포인터로 직접 결합 가능
배열을 이용하게되면 첨자를 조작하여 간접적으로 연결해야 함
- 링크를 저장할 공간을 필요로하지 않는 장점을 가짐
- 불균형 트리의 경우 빈 노드를 위해서도 배열 공간을 확보해야 함
- 따라서 균형 트리(balanced tree)에 대해서 배열을 이용한다
힙은 균형 트리이므로 배열을 이용하는 것이 유리함
■ 힙 정렬의 방법
▷ 힙을 생성
- 힙의 크기를 배열의 크기로 하고 BuildHeap을 통해 힙조건에 맞게 수정하는 방식
- 배열에 저장은 초기 자료의 순서대로 힙이라 가정하고 트리로 구성함
― 부모 노드는 항상 두 자식 보다 큰 값을 가짐
- BuildHeap을 통해 하나씩 제자리를 찾아 내려보냄
▷ 제거 동작을 반복 수행
― 가장 큰 값을 갖는 루트에서 제거 동작을 수행하고
― 루트가 없는 힙에서는 최단말 노드가 임시로 루트가 되며 제자리를 찾아 내려가게 됨
― 루트에서 뽑아낸 자료는 임의 배열에 끝에서부터 차례로 저장함
■ 힙 정렬 알고리즘
-------------------------------------------------------------------------------
#define LeftChild(i) (2*(i))
void PercDown (int A[ ], int i, int N) /* BuildHeap 수행*/
{
int Child, Temp; /*Temp는 루트의 값을 보관 */
/*1*/ for(Tmp=A[i]; LeftChild(i)<=N; i=Child)
{
/*2*/ Child=LeftChild(i);
/*3*/ if(Child!=N && A[Child+1] > A[Child])
/*4*/ Child++;
/*5*/ if( Temp<A[Child]) /* 루프를 돌면서 루트의 값이 */
/*6*/ A[i]=A[Child]; /* 자기의 위치로 내려옴 */
else
/*7*/ break;
}
/*8*/ A[i]=Temp;
}
void Heapsort(int A[ ],int N)
{
int i;
/*a*/ for( i = N/2; i > 0; i--) /* BuildHeap 호출*/
/*b*/ PercDown(A, i, N);
/*c*/ for( i = N; i >= 2; i--)
{
/*d*/ Swap(&A[1], &A[i]); /* DeleteMax 루트의 값을 제일 뒤로 */
/*e*/ PercDown(A, 1, i-1); /* 제일 뒤에 있던 값이 루트에서 자기 위치로 */
} /* BuildHeap 호출*/
}
-------------------------------------------------------------------------------
■ 성능
▷ MaxHeap을 만들어서 DeleteMax를 반복 수행하여 정렬
▷ N을 입력 파일의 크기라 하면 BuildHeap O(N), N번 DeleteMax O(NlogN)
▷ BuildHeap은 내부노드(총 N/2개)에서만 수행되면 됨
- 단말노드는더이상내려갈곳이없으므로을적용할필요가없음
- N/2 노드(마지막 내부노드 위치)부터 뿌리 노드까지만 적용되면 됨
- 적용 범위가 반으로 줄었기 때문에 성능면에서 크게 향상된다. O(NlogN)
▷ 이론적으로 이상적인 O(NlogN)이나 실제 수행시간 길다.
▷ 뛰어난 성능을 가지면서도 추가적인 메모리를 필요로 하지 않음
자료 출처 : http://www.dreamy.pe.kr/zbxe/codeclip/5944