[자료구조](16)[힙 구현]

 

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;
}