힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 **완전이진트리(Complete binary tree)**를 기본으로 한 자료구조(tree-based structure)이다. (위키백과 )
- Heap Sort 정렬 알고리즘
- Priority Queue
- Graph Algorithm : Dijkstra, Prim's Minimum Spanning Tree(프림 최소 신장 트리)
그리고 다양한 문제를 푸는데에서 사용된다.
부모노드의 키값이 자식노드의 키값보다 항상 작거나 같다. key(부모노드) < key(자식노드)
부모노드의 키값이 자식노드의 키값보다 항상 크거나 같다. key(부모노드) > key(자식노드)
따라서 루트노드에는 항상 가장 큰 값이나 가장 작은 값이 저장되어 있기때문에 최대값 또는 최솟값을 O(1)만에 찾을 수 있다. 여기서 키값은 오로지 부모 자식노드간에만 성립한다.
n개의 노드를 가지고 있는 heap의 높이는 O(logn)이다. 힙은 완전이진트리이므로 노드의 개수로 깊이와 높이를 계산할 수 있다.
마지막 level을 제외하고는 각 레벨 i에 2^i개의 노드가 존재한다.
힙은 완전이진트리이므로 각 노드에 번호를 붙일 수 있다. 배열은 완전이진트리를 표현하기에 매우 효율적이다.
배열로 표현함으로써 부모노드와 자식노드를 찾기가 쉬워진다.
-
왼쪽 자식노드 인덱스 :
2*(부모노드 인덱스)
-
오른쪽 자식노드
2*(부모노드 인덱스)+1
-
노드 x의 부모 노드 인덱스는
(자식노드 인덱스)/2
로 알 수 있다.
주의사항 **index는 1부터 시작!**한다는 점을 주의해야한다.
- 가장 끝의 자리에 노드를 삽입한다.
- 그 노드와 부모 노드를 서로 비교한다.
- 규칙(최소힙, 최대힙)에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다.
- 규칙에 맞을 때까지 1~3번 과정을 반복한다.
- O(logn)
최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다.
- 루트 노드를 제거한다.
- 루트 자리에 가장 마지막 노드를 삽입한다.
- 올라간 노드와 그의 자식 노드(들)와 비교한다.
- 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.
-
최대 힙
- 부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.
- 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.
- 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.
-
최소 힙
- 부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.
- 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.
- 부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.
- 조건을 만족할 때까지 4의 과정을 반복한다.
- O(logn)
#include <stdio.h>
#define MAX 1000000
typedef struct{
int heap[MAX];
int hsize;
}Heap;
void init(Heap * h){
h->hsize=0;
}
void insert(Heap * h, int key){
int p; //현재 위치 저장
// 마지막 위치에 추가
h->heap[++(h->hsize)]=key;
// 위치 조정
p=h->hsize;
while((h->heap[p/2])>key){
h->heap[p] = h->heap[p/2];
p/=2;
}
h->heap[p]=key;
}
int delete(Heap * h){
int min,last,child,i;
//루트노드값이 최소
min = h->heap[1];
last = h->heap[(h->hsize)--];
for(i=1; i*2<=h->hsize; i=child){
child = i*2;
if(child!=h->hsize && h->heap[child+1]<h->heap[child])child++;
if(last>h->heap[child])h->heap[i]=h->heap[child];
else break;
}
h->heap[i]=last;
return min;
}
int main(int argc, const char * argv[]) {
Heap heap;
int min;
init(&heap);
insert(&heap, 10);
insert(&heap, 5);
insert(&heap, 30);
for(int i=1;i<=heap.hsize;i++){
printf("%d ",heap.heap[i]);
}
min = delete(&heap);
printf("\n%d \n",min);
for(int i=1;i<=heap.hsize;i++){
printf("%d ",heap.heap[i]);
}
min = delete(&heap);
printf("\n%d \n",min);
for(int i=1;i<=heap.hsize;i++){
printf("%d ",heap.heap[i]);
}
return 0;
}
#include <stdio.h>
#define MAX 100
typedef struct{
int heap[MAX];
int hsize;
}Heap;
void init(Heap * h){
h->hsize=0;
}
void insert_max(Heap * h, int key){
int p; //현재 위치 저장
p=++(h->hsize);
// 마지막 위치에 추가
h->heap[p]=key;
// 위치 조정
while((h->heap[p/2])<key){
if(p==1)break;
h->heap[p] = h->heap[p/2];
p/=2;
}
h->heap[p]=key;
}
int delete_max(Heap * h){
int max,last,child,i;
//루트노드값이 최소
max = h->heap[1];
last = h->heap[(h->hsize)--];
for(i=1; i*2<=h->hsize; i=child){
child = i*2;
if(child!=h->hsize && h->heap[child+1]>h->heap[child])child++;
if(last<h->heap[child])h->heap[i]=h->heap[child];
else break;
}
h->heap[i]=last;
return max;
}
int main(int argc, const char * argv[]) {
Heap heap;
int max;
init(&heap);
insert_max(&heap, 10);
insert_max(&heap, 5);
insert_max(&heap, 30);
for(int i=1;i<=heap.hsize;i++){
printf("%d ",heap.heap[i]);
}
max = delete_max(&heap);
printf("\n%d \n",max);
for(int i=1;i<=heap.hsize;i++){
printf("%d ",heap.heap[i]);
}
max = delete_max(&heap);
printf("\n%d \n",max);
for(int i=1;i<=heap.hsize;i++){
printf("%d ",heap.heap[i]);
}
return 0;
}