힙 정렬의 "힙" 은 두가지 용어로 사용된다.
첫번째는 자료구조 힙이고, 두번째는 메모리공간 힙이다.
여기서는 자료구조 힙에 대해 논의한다.
힙이란 간단하게 두가지 힙이 존재한다. 최대힙과 최소힙이다.
(피보나치힙은 제외)
최대힙의 정의는 부모노드의 값은 반드시 자식노드의 값보다 크고, 완전 이진트리의 형태를 띈다.
최소힙은 그 반대의 경우이다.
여기서 힙을 실제로 노드기반 자료구조로 표현할 수 도있지만, 이는 멍청한 짓이다.
그 첫번째 근거는, 노드기반 자료구조의 가장 큰 단점인 메모리할당 함수의 수행시간이다.
당연한 이야기지만, 시스템콜인 할당함수는 매우 많은 시간이 소요된다.
둘째로 힙정렬에서 사용되는 힙은 입력값이 배열이다. 즉 결과도 배열인데, 그 중간 연산으로
노드기반 힙을 사용할 이유가 없다.
따라서 이를 배열로 표기하는데, 부모와 왼쪽자식, 오른쪽 자식을 찾는 프로시저를 다음과 같이 정의 할 수 있다.
#define HEAP_PARENT(I) (((I)-1)>>1)
#define HEAP_LEFT(I) (((I)<<1)+1)
#define HEAP_RIGHT(I) (((I)<<1)+2)이는 인라인함수나 매크로로 작성하는것이 좀더 좋다.
우선 힙 정렬 알고리즘에서는 최대힙을 사용한다.(오름차순 정렬일 경우엔)
힙은 완전 이진트리를 기반으로 하므로, 원소의 개수가 n 개일때 높이는 O(lg n) 이다.
이제 몇가지 문제를 풀어보자.
1.높이가 h인 힙의 최대,최소 원소 수는 얼마인가?
- 원소가 n개이면 높이는 lg n 개이다. 이 높이를 h로 치환하자.
- 높이는 0부터 시작하므로, 간단하게 2^h ~ 2^(h+1) - 1 임을 알 수 있다.
2.원소수가 n인 힙의 높이는 lower(lg n) 임을 보여라( lower은 하한을 뜻한다)
- 1번 문제에서 원소수가 n일때 n의 범위는 2^h <= n <= 2^(h+1) - 1 임을 보였다.
- 이 부등식을 풀면 log2( (n+1) / 2 ) <= h <= log2(n) 이 나온다.
- 즉 log2(n) 의 하한이 맞다.
3.최대 힙의 모든 서브 트리에서 서브 트리의 루트가 그 서브 트리에서 최댓값을 가짐을 보여라.
- 서브트리의 개념을 안다고 가정하고 설명한다.
- 이는 힙의 특성을 묻는 질문이다. 힙의 특성중 임의의 노드는 절대로 그 노드의 부모 노드보다 클 수 없다.
4.최대 힙에서 모든 원소가 서로 다를때 가장 작은 원소는 어디에 존재 하겠는가?
- 알수없다. 원래의 배열의 순서에 따라 달라진다.
- 이 문제의 정답을 마지막 층에 있다고 한다면 틀린다.
- 꽉찬 완전 이진트리라고 하지 않았으므로, 자식이 없는 노드, 즉 leaf 노드라고 해야 이 문제의 정답이다.
5.정렬된 배열은 최소 힙인가?
- 그렇다. 힙의 부모는 n/2 로 찾는데 이는 실제배열의 앞쪽이다. 이는 정렬되어 있으므로, 반드시 자신의 값보다 작음을 보장한다. 따라서 정렬된 배열은 최소힙이다.
- 반대로 역순정렬된 배열은 최대 힙이다.
6.수열 { 23, 17, 14, 6, 13, 10, 1, 5, 7, 12}는 최대 힙인가?
- 아니다. 그림을 그려보면 (7) 의 부모가 (6)으로 최대힙이 아님을 쉽게 알 수 있다.
7.원소 수가 n개인 힙을 배열로 나타낼 때 lower(n/2)+1 , lower(n/2) +2 .....n번째 노드가
리프 임을 보여라.
- 문제가 ㅈ나 이상한데....아마 수열이 인덱스를 나타내는것이 아니지 싶다.
- 우선 lower(n/2)는 힙의 중간 어디쯤을 나태낼터인데, 거기에 +1 +2 +3 ... +n은
- 배열을 초과함을 뜻하는데,,,뭔소린지 솔직히 잘 모르겠다.
그럼 이제 , 힙을 만드는 함수를 정의하여 보자.
힙을 만드는 방식은 두가지가 있다. 상향식 방법과 하향식 방법이다.
당연히 ! 상향식 방법이 더 간단하고 속도도 빠르다. 일반적으로 힙을 구성할때는 상향식 방법을 쓰고, 힙정렬을 할땐 하향식 방법을 사용한다.
상향식 방법은 루트쪽으로 가면서 검사하는 방법이고 , 하향식 방법은 리프쪽으로 가면서 검사하는 방법이다.
//build heap down to up ( this function is use in forword loop )
#define HEAPIFY_D2U(ARRAY,I,ELEM_SZ,COMPARE) do{\
int IDX=I;\
while(IDX>0 && COMPARE(&ARRAY[IDX],&ARRAY[HEAP_PARENT(IDX)])>0){\
SWAP(ARRAY[IDX],ARRAY[HEAP_PARENT(IDX)],ELEM_SZ);\
IDX=HEAP_PARENT(IDX);\
}\
}while(0)
//build heap up to down ( this function is use in reverse loop )
#define HEAPIFY_U2D(ARRAY,INDEX,ELEM_SZ,BOUND,COMPARE) do{\
int IDX=INDEX;\
int L,R,C;\
do{\
L=HEAP_LEFT(IDX);\
R=HEAP_RIGHT(IDX);\
if(L<BOUND && COMPARE(&ARRAY[L],&ARRAY[IDX])>0)C=L;\
else C=IDX;\
if(R<BOUND && COMPARE(&ARRAY[R],&ARRAY[C])>0)C=R;\
if(C==IDX)break;\
SWAP(ARRAY[C],ARRAY[IDX],ELEM_SZ);\
IDX=C;\
}while(1);\
}while(0)매크로 함수인데, COMPARE에 비교 함수를 넣어도 되고, 매크로 비교함수를 넣어도 좋다.
#include<stdio.h>
#include<time.h>
#include"sort/heap.h"
#define MAXN 10000000
typedef struct Z{
#define Z_COMPARE(A,B) ((A).a < (B).a)
int a; //primary key
int b;
int c;
}Z;
int main() {
Z *arr=(Z*)calloc(MAXN,sizeof(Z));
int i;
for (i = 0; i < MAXN; i++) {
arr[i].a = rand() % (MAXN * 10);
arr[i].b = rand() % (MAXN * 10);
arr[i].c = rand() % (MAXN * 10);
}
for (i = MAXN/2; i >= 0; i--)
HEAPIFY_U2D(arr, i, sizeof(Z), MAXN, Z_COMPARE);
free(arr);
return 0;
}
위는 사용 예시이다.
힙을 만드는데 만일 상향식 방법인 D2U를 사용한다면 모든 원소에대해 구성을 해야한다.
하지만 하향식 방법을 사용한다면, n/2 부터 0 까지만 돌면된다.
근데!!! 하향식 방법이 좀더 빠르다
이를 힙을 만든다. 라고 표현을 한다.
HEAPIFY는 복잡도가 lg n임을 증명할 수 있다.
그리고 이를 n/2 번 반복한다. 이를 복잡도가 n lg n 이라고 말할수도 있지만, 좀더 좋은 방법이 있다.
먼저 원소가 n개 있을때 이 힙의 높이는 lower(lg n)임을 보였다.
그리고 높이가 h인 노드수는 upper(n / 2^(h+1) ) 임을 보일 수 있다.
- 원소의 개수가 2^h 에서 2^(h+1) - 1 사이에 있을때
- 이는 루트의 높이가 h임을 문제 1번에서 증명하였다. (다시 말하지만 높이는 0부터 시작한다)
- 따라서 그리고 이 원소의 개수는 높이가 1증가할수록 높이h의 원소는 2배 씩 증가한다.
- =따라서 2^n+1을 분모로 놓게되면 알맞은 공식이 완성된다.
이를 근거로 하여 힙을 구성하는 함수의 복잡도를 다음과 같이 쓸 수 있다.
sigma h 0 to lower(lg n) (upper(n/2^(h+1)) * O(h)
이는 O(n* sigma h 0 to lower(lg n) (h/2^h) )
따라서 이 공식은 sigma k=0 to INF (kx^k) 는 x/(1-x)^2 의 공식에 따라
x에 1/2를 대입하여 풀 수 있다.
따라서 이 힙만드는 함수의 복잡도는 선형시간에 동작한다고 말할 수 있다.
이를 코드로 표현하면 아래와 같다.
#define BUILD_HEAP(ARRAY,ELEM_SZ,LENGTH,COMPARE) do{\
int i=(LENGTH)>>1;\
while(i--) {HEAPIFY_U2D(ARRAY,i,ELEM_SZ,LENGTH,COMPARE);}\
}while(0)이제 힙소트를 구현하면 아래와 같다.
#define IMPLEMENT_HEAPSORT(TYPE)\
void ATTATCH(heapsort_,TYPE)(TYPE* base,int size,int(*COMPARE)(const TYPE*,const TYPE*)){\
int i=size;\
int hsz=size;\
BUILD_HEAP(base,sizeof(TYPE),size,COMPARE);\
while(i-- > 0){\
SWAP(base[0],base[i],sizeof(TYPE));\
--hsz;\
HEAPIFY_U2D(base,0,sizeof(TYPE),hsz,COMPARE);\
}\
}\마치 C++의 템플릿 처럼 모든 자료형에 대한 최적화된 소스를 생성한다.
제네릭한 소트는 C에서 void* 를 사용하여 구현하는데, 많이 짜본 사람들은 이 방법의 단점을 알것이다.
제네릭한 만큼 시간이 소요되는데...
본 매크로함수의 시간은 좀 더 테스트를 해봐야겠다.
stdlib.h 의 qsort 와의 비교에서는 2배정도 느린 결과를 보여주었다.
자 이제 이걸 개선해보자.
버블정렬이 선택정렬로
gnome정렬이 삽입정렬로 개선되는 방식의 swap 없애기 기법을 통해 개선을 하면
속도는 다음과 같이 개선된다.
gcc -O3
갱신전
array make time : 0.021289
array size : 1000000
quicksort : 0.177737
heapsort : 0.348398
갱신후
array make time : 0.022693
array size : 1000000
quicksort : 0.188064
heapsort : 0.264053