힙 (자료 구조)
위키백과 ― 우리 모두의 백과사전.
힙(Heap)은 내부노드(internal node)에 키와 요소(key,element)를 저장한 이진트리로 다음과 같은 두가지 특징을 갖는 것을 말한다.
트리를 T, 임의 내부노드를 v 라고 하면 다음과 같다:
- 뿌리노드를 제외한 각 내부노드는
또는
이다. (즉, 키 값은 오름차순이거나 내림차순이다.) - 마지막 왼쪽 결합 노드들의 레벨을 제외한 다른 모든 레벨들은 완전 이진트리를 형성한다. (즉, 레벨 포화 상태 : saturated status on level)
힙 리스트(heap list)로 표현할 때 i번째 노드의 왼쪽 자식노드(left kindnode)의 위치는 2i가되며,i번쨰 노드의 오른쪽 자식노드(right kindnode)의 위치는 2i+1이고, 또한 i번째 부노드의 위치는 i/2가 된다.
힙에는 내림차순인 최대힙과 오름차순인 최소힙이 있으며 개략적인 과정은 아래와 같다.
목차 |
[편집] 자바 의사코드로 짠 최대힙
algorithm upHeap(Posion v): while (not isRoot(v)) and key(parent(v))>key(v) do { swapItems(v.parent(v)); v<-parent(v); }
[편집] 자바 의사코드로 짠 최소힙
algortihm downHeap(Positon v): while not (isExternal(leftChild(v)) and isExternal(rightChild(v)) do { if isExternal(rightChild(v)) tehn v<-leftChild(v) else if key(leftChild(v))<=key(rightChild(v)) then v<-leftChild(v) else v<-rightChild(v); if key(parent(v)) > key(v) then swapItems(v,parent(v)) else break; }
[편집] 예제
다음의 내용의 테이블을 최대힙으로 정렬해 본다. [H|E|A|P|S|O|R|T]
이 테이블을 사전순으로 정렬(즉 A<B<C<…<Y<Z)한다면 다음과 같다.
1 2 3 4 5 6 7 8
H E A P S O R T //중간지점인 p(4번째 인덱스)에서 시작
^ ^ //그의 자식은 (왼쪽 자노드 인덱스8)T>P이기 때문에 교환
H E A T S O R P //A(3번째 인덱스)로 계속되며 A의 왼쪽 자노드는 O(6번쩨 인덱스)가 되며 오른쪽 자노드는
^ ^ ^ //R(7번째 인덱스값)이 되는데 R>O,R>A이므로 R,A교환
H E R T S O A P //E(인덱스 2)와 그 왼쪽 자노드T(인덱스 4),오른쪽 자노드S(인덱스 5)비교
^ ^ ^ //T>S,T>E 결국 T,E교환
H T R E S O A P //계속 E(인덱스 4)는 왼쪽 자노드P(인덱스 8)과 비교교환한는데 P>E
^ ^
H T R P S O A E //H(인덱스 1)은 그의 왼쪽 자노드T(인덱스 2)와 오른쪽 자노드R(인덱스 3)
^ ^ ^ //T>R,T>H비교 교환한다.
T H R P S O A E //계속 H를 비교 교환하게 되는데,H(인덱스 2)이므로 왼쪽 자노드P(인덱스 4),오른쪽 자노드
^ ^ ^ //S(인덱스5)에서 S>P,S>H비교 교환하게 된다.
T S R P H O A E //정렬끝.
[편집] 알고리즘
[편집] adjusting full binary tree to heap tree in JAVA
makeTreeHeap(H,n) //H full binary Tree,data size n for(i <= H/2;i>=1;i <- i-1) do //부모노드 레벨의 역행(4-,3-,2-,1번쨰) { p <- i;// 중간지점에서 시작 for(j<- 2*p;i<=n;j <- 2*j)do //해당 부모노드의 자식노드들에 대한 비교 교환 { if(j<n) then if(H[j] < H[j+1]) then j <- j+1 if(H[p] >= H[j] exit; temp <- H[p]; H[p] <- H[j]; H[j] <- temp; p <- j; } }
[편집] C로 짠 최대 힙정렬
void hsort(int a[],int n) //need to be changed. { int i,temp; for(i=n/2-1;i>=0;i--) makeTreeHeap(i,n); for(i=n-1;i<=1;i--) { temp=a[i];a[i]=a[0];a[0]=temp; makeTreeHeap(1,i-1); } }
[편집] 복잡도
힙의 시간복잡성은 O(logn)이다,왜냐면 이진트리의 속성
에서, 우리는
이므로 힙트리의 높이가 h = log2(n + 1) = O(log2n)됨을 알수있다.
[편집] C 소스코드
아래의 소스코드는 큰것이 위로 가도록 하는 최대힙을 C언어로 구현한 것이다.
void swap(int *a,int *b) { int tmp; tmp=*a; *a=*b; *b=tmp; } int max(int a,int b,int c) { int max=0,q; if(tree[a]>max) { max=tree[a]; q=a; } if(tree[b]>max) { max=tree[b]; q=b; } if(tree[c]>max) { max=tree[c]; q=c; } return q; } void create_heap() { end=N/2; for(i=end;i>=1;i--) { nnow=i; while((qq=max(nnow,nnow*2,nnow*2+1))!=nnow) { swap(&tree[nnow],&tree[qq]); nnow=qq; } } }

