[자료구조] Heap

우선순위 큐

저장순서에 상관없이 우선순위로 뽑아냄

delete(q)	우선순위가 가장 높은 요소 삭제
find(q)	우선순위가 가장 높은 요소 반환

 

최소 우선순위 큐(min heap): 값이 작은 노드가 우선순위가 높다

최대 우선순위 큐(max heap): 값이 큰 노드가 우선순위가 높다

 

배열을 이용한 우선순위 큐

연결리스트를 이용한 우선순위 큐

heap을 이용한 우선순위 큐(best)

---

heap 

부모노드의 priority >= 자식노드의 priority인 완전이진트리(중복허용)

n개의 노드를 가지고 있는 heap의 높이는 O(logn)

 

배열을 이용하여 구현

주의: 인덱스가 가장 크다고 우선순위가 가장 낮은 건 아님

 

삽입 - O(logn)

일단 마지막 노드에 이어서 삽입, 성질을 만족하게 부모 노드와 교환

void insert_max_heap(HeapType* h, element item){
    int i;
    i = ++(h->heap_size); //일단 맨 마지막에 삽입
    
    //부모 노드보다 클 때
    while((i != 1) && (item->key > h->heap[i/2]->key)){
        h->heap[i] = h->heap[i/2]; //갈아끼우기
        i /= 2;
    }
    h->heap[i] = item; //정한 인덱스에 삽입
}

 

삭제 - O(logn)

루트 노드 삭제, 일단 마지막 노드를 루트 노드로 이동, 루트에서 단말 노드까지 성질을 만족시키게 교환

element delete_max_heap(HeapType* h){
    int parent, child; //지금 보고 있는 두 노드 번호
    element item, temp;
    
    item = h->heap[1]; //root
    temp = h->heap[(h->heap_size)--]; //말단노드
    
    parent = 1;
    child = 2;
    
    while((child <= h->heap_size){
        //오른쪽 자식이 우선순위가 더 클 때
        if((child < h->heap_size) && (h->heap[child]->key) < h->heap[child+1]->key)
            child++;
        //말단노드보다 더 작은 노드를 찾음
        if(temp->key >= h->heap[child]->key) break;
        
        //지금 보고 있는 두 노드가 밑에 두 노드로 바뀜
        h->heap[parent] = h->heap[child]; 
        parent = child;
        child *= 2;
    } 
    
    //말단보다 작은 애를 찾았기 때문에
    //parent 자리에 말단 노드를 넣음
    h->heap[parent] = temp;
    return item; 
}

---

히프 정렬 - O(nlogn)

정렬해야 할 n개의 요소들을 max heap에 삽입

한번에 한 요소를 heap에서 삭제하여 저장

void heap_sort(element a[], int n){
    HeapType* h;
    
    h = create();
    init(h);
    
    //다 넣고
    for(int i = 0; i < n; i++){
        inser_max_heap(h, a[i]);
    }
    //하나씩 빼서 저장
    for(int i = (n-1); i >= 0; i--){
        a[i] = delete_max_heap(h);
    }
    free(h);
}

 

LPT (longest processing time first)

가장 오래 걸리는 일을 가장 available time이 가장 빨리 쓸 수 있는 기계에 할당

다 쓴 기계는 available time을 변경하고 min_heap에 다시 넣기

#define MACHINES 3 //기계의 개수

typedef struct{
    int id;
    int avail; //종료시간 + 1
}element;

int main(void){
    int jobs[JOBS] = {8,7,6,5,3,2,1}; //작업은 정렬되어 있다고 가정
    element m = {0, 0};

    HeapType* h;
    h = create();
    init(h);

    for(int i = 0; i < MACHINES; i++){
        m->id = i+1;
        m->avail = 0;
        insert_min_heap(h,m);
    }
    
    for(int i = 0; i < JOBS; i++){
        m = delete_min_heap(h);
        m->avail += jobs[i];
        insert_min_heap(h,m);
    }
    
    return 0;
}

---

허프만 코드 

각 글자의 빈도를 알때 이진트리(heap)를 이용하여 정보손실 없이 압축

가장 자주 등장하는 알파벳을 가장 작은 bit로 표현

빈도수가 가장 적은 알파벳이 root에서 가장 먼 leaf에 있도록 구성

typedef struct{
    TreeNode* ptree;
    char ch;
    int key;
}element;

int is_leaf(TreeNode* root){
    return !(root->left) && !(root->right);  
}

void huffman_tree(int freq[], char ch_list[], int n){
    int i;
    TreeNode* node, *x;
    HeapType* heap;
    element e, e1, e2;
    int codes[100];
    int top = 0;
    
    heap = create();
    init(heap);
    for(int i = 0; i < n; i++){
         node = make_tree(NULL, NULL);
         e.ch = node->ch 
    }
}

void print_codes(TreeNode* root, int codes[], int top){
    if(root->left){
        codes[top] = 1;
        print_codes(root->left, codes, top+1);
    }
    if(root->right){
        codes[top] = 0;
        print_codes(root->right, codes, top+1);
    }
    if(is_leaf(root)){
        printf("%c", root->ch);
        print_array(codes, top);
    }
}