heap
완전 이진트리니 배열로 구현하기 편하다.
(자료구조 12 참고)
여기서는 계산상의 편의를 위해 1부터 인덱싱하는 Max힙을 만들겠다.
기본 골조
자료를 저장할 배열을 만든다.
#define MAX_SIZE 100
int heap[MAX_SIZE];
int heapSize = 0;
그리고 인덱스에 있는 값을 바꿔야 하므로, swap도 정의하겠다.
void swap(int* a, int* b){
int tmp = *a;
*a = *b;
*b = tmp;
}
부모-자식 연산
인덱스를 가지고 부모 or 자식의 인덱스 계산
int parent(int i){
return i/2;
}
int left(int i){
return 2*i;
}
int right(int i){
return 2*i+1;
}
bulid
여기서는 시간복잡도가 더 나은 bubbling down 방식으로 만든다.
void heapify(int i){
int largest = i;
int l = left(i);
int r = right(i);
//범위 체크 && 힙이 깨져 있는가?
if (l<=healSize && heap[l]>heap[largest]) {largest = l;}
if (r<=healSize && heap[r]>heap[largest]) {largest = r;}
if (largest != i) {
swap(&heap[i], &heap[largest]);
heapify(largest);
}
}
void bulid(){
for (int i = parent(heapSize); i>=1; i--){
heapify(i);
}
}
insert
인덱스의 맨 마지막에 집어넣고 bubbling up
void insert(int value){
int i = ++heapSize; //1부터 시작하는 인덱스
heap[i] = value; // 1. 맨 끝에 넣고
// root에 도달 전 && 힙 성질이 아직 깨짐
while(i>1 && heap[i]>heap[parent(i)]){
swap(&heap[i], &heap[parent(i)]); // 2. 바꾸기
i = parent(i);
}
}
delete
인덱스의 맨 마지막 값을 앞으로 옮기고 bubbling down
(bulid에서 썼던 방식과 똑같다)
int delete(int del_index){
if (heapSize == 0 || del_index>heapSize) {return -1;}
//힙이 비어있거나 지울 인덱스가 범위를 벗어나면 -1 반환
int max = heap[del_index];
heap[del_index] = heap[heapSize--];
int i = del_index;
while(1){
int l = left(i);
int r = right(i);
int largest = i;
//범위 체크 && 힙이 깨져 있는가?
if (l<healSize && heap[l]>heap[largest]) {largest = l;}
if (r<healSize && heap[r]>heap[largest]) {largest = r;}
if (largest == i) {break;}
swap(&heap[i], &heap[largest]);
i = largest
}
return max;
}
728x90
반응형
'CS > 자료구조' 카테고리의 다른 글
[자료구조](18)[map & 해시함수] (0) | 2025.05.21 |
---|---|
[자료구조](17)[trie] (0) | 2025.05.20 |
[자료구조](-)[힙 생성의 시간복잡도는 O(n)?] (0) | 2025.05.15 |
[자료구조](15)[우선순위 큐 & 힙] (0) | 2025.05.14 |
[자료구조](14)[이진트리의 구현 3] (0) | 2025.05.09 |