자료구조 2. 우선순위 큐 & 힙(Heap)

 

 

 

 

 

 

 

1. 우선순위 큐 란?

: 우선 순위를 가진 항목들을 저장하는 큐이다. 

우선 순위가 높은 데이터가 먼저 삭제된다.

 

 

 

 

 

1) 구현 방법

- 배열 이용

- 연결 리스트 이용

- 힙(Heap) 이용 -> 가장 효율적이다.(트리 구조)

 

 

 

 

 

 

 

 

 

2. 힙(Heap) 이란?

: 노드들이 아래의 식을 만족하는 완전이진트리이다.

key(부모 노드) >= key(자식 노드)

 

 

* 완전이진트리 : 왼쪽부터 차례대로 이진트리를 꽉 채운 트리이다. 

 

1) 힙의 종류

- 최대 힙 : key(부모 노드) >= key(자식 노드)

- 최소 힙 : key(부모 노드) <= key(자식 노드)

 

 

 

2) 힙의 높이

: N 개의 노드를 가지고 있는 힙의 높이는 O(logN) 이다.

 

 

3) 힙의 구현방법

: 배열로 구현한다. 완전이진트리이므로 각 노드에 번호를 붙일 수 있다. 이 번호를 배열의 인덱스로 생각한다. 

 

* 배열로 트리구조 구현할 때 장점 - 부모노드를 쉽게 찾을 수 있다.

왼쪽 자식 인덱스 = (부모의 인덱스) * 2

오른쪽 자식 인덱스 = (부모의 인덱스) * 2 + 1

부모의 인덱스 = (자식의 인덱스) / 2

 

 

 

 

4) 기본 코드

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
typedef struct {
    int key;
} element;
typedef struct {
    element heap[MAX_ELEMENT];
    int heap_size;
} HeapType;


HeapType* create()
{
    return (HeapType*)malloc(sizeof(HeapType));
}

void init(HeapType* h)
{
    h->heap_size = 0;
}

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;     // ªı∑ŒøÓ ≥εÂ∏¶ ª¿‘
}

element delete_max_heap(HeapType* h)
{
    int parent, child;
    element item, temp;

    item = h->heap[1];
    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;
    }
    h->heap[parent] = temp;
    return item;
}

void preorder1(HeapType *h, int root){
    if(root > h->heap_size)
        return;
    
    printf("%d ", h->heap[root].key);
    preorder1(h, root * 2);
    preorder1(h, root * 2 + 1);
}

void print_heap(HeapType *h){
    int num = 4;
    
    printf("%d\n", h->heap[1].key);
    
    for(int i=2; i<=h->heap_size; i++){
        printf("%d ", h->heap[i].key);
        if((i+1) == num){
            printf("\n");
            num *= 2;
        }
    }
    printf("\n");
}

int max(int a, int b){
    if (a >= b)
        return a;
    else
        return b;
}

int find(HeapType *h, int root, int key){
    if(root > h->heap_size)
        return 0;
    if(h->heap[root].key == key)
        return root;
    else if (h->heap[root].key < key)       // 중요
        return 0;
    
    return max(find(h, root * 2, key), find(h, root * 2 + 1, key));     // 중요
}

void print_sorted_value(HeapType *h){
    int size = h->heap_size;
    element e[10];
    
    for(int i=0; i< size; i++){
        e[i] = delete_max_heap(h);
        printf("%d ", e[i].key);
    }
    for(int i=0; i< size; i++){
        insert_max_heap(h, e[i]);
    }
    printf("\n");
}

void modify_priority(HeapType *h, int oldKey, int newKey){
    
    int i, child;
    
    if(oldKey == newKey)
        return;
    
    i = find(h, 1, oldKey);
    if(i == 0)
        return;
    
    if(newKey > oldKey){
        
        while ((i != 1) && (newKey > h->heap[i / 2].key)) {
            h->heap[i] = h->heap[i / 2];
            i /= 2;
        }
        h->heap[i].key = newKey;     // ªı∑ŒøÓ ≥εÂ∏¶ ª¿‘
        
    } else {
        element temp = h->heap[(h->heap_size)];
        
        child = i * 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[i] = h->heap[child];
            i = child;
            child *= 2;
        }
        h->heap[i] = temp;
    }
}

int main(void)
{
    element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
    element eA = { 9 }, eB = { 19 }, eC = { 39 };
    element e4, e5, e6;
    int index;
    int key, oldKey, newKey;
    HeapType* heap;
    
    heap = create();
    init(heap);    // √ ±‚»≠

    printf("Step1 : 삽입된 10, 5, 30에 추가적으로 9, 19, 39를 삽입한다\n");
    insert_max_heap(heap, e1);
    insert_max_heap(heap, e2);
    insert_max_heap(heap, e3);
    insert_max_heap(heap, eA);
    insert_max_heap(heap, eB);
    insert_max_heap(heap, eC);
    
    printf("\nStep2 : preorder, print_heap 함수 테스트\n");
    preorder1(heap, 1);
    printf("\n");
    print_heap(heap);
    
    
    e4 = delete_max_heap(heap);
    printf("삭제 : %d 루트가 삭제됨\n", e4.key);
    print_heap(heap);
    
    printf("\nStep3 : find 함수 테스트\n");
    printf("찾을 key 입력(-1 for exit) : ");
    scanf("%d", &key);
    while(key != -1){
        if((index = find(heap, 1, key)) == 0)
            printf("%d는 없음\n", key);
        else
            printf("%d은 [%d]에 있음\n", key, index);
        printf("찾을 key 입력(-1 for index) : ");
        scanf("%d", &key);
    }
    
    printf("\nStep4 : print_sorted_value 함수 테스트\n");
    print_sorted_value(heap);
    
    
    printf("\nStep5 : modify_priority 함수 테스트\n");
    printf("바꿀 key 입력(-1 for exit) : ");
    scanf("%d", &oldKey);
    while(oldKey != -1){
        printf("새 key 입력 : ");
        scanf("%d", &newKey);
        modify_priority(heap, oldKey, newKey);
        print_heap(heap);
        
        printf("바꿀 key 입력(-1 for exit) : ");
        scanf("%d", &oldKey);
    }

    free(heap);
    return 0;
}

 

 

 

 

 

 

5) 삽입 연산

- 힙의 마지막 노드에 이어서 삽입한다.

- 삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

 

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;     // ªı∑ŒøÓ ≥εÂ∏¶ ª¿‘
}

 

 

 

 

 

 

6) 삭제 연산

- 루트 노드를 삭제한다.

- 마지막 노드를 루트 노드로 이동시킨다.

- 루트에서부터 단말 노드까지의 경로에 있는 노드들을 교환하여 힙의 성질을 만족시킨다.

 

element delete_max_heap(HeapType* h)
{
    int parent, child;
    element item, temp;

    item = h->heap[1];
    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;
    }
    h->heap[parent] = temp;
    return item;
}

 

 

 

 

 

 

 

 

7) Find 연산

int find(HeapType *h, int root, int key){
    if(root > h->heap_size)
        return 0;
    if(h->heap[root].key == key)
        return root;
    else if (h->heap[root].key < key)       // 중요
        return 0;
    
    return max(find(h, root * 2, key), find(h, root * 2 + 1, key));     // 중요
}

 

- 기준 인덱스가 힙의 크기보다 크면 이미 힙을 초과한 것이므로 0을 반환한다.

- 키 값이 동일하면 기준 인덱스를 반환한다.

- 기준 노드의 값이 찾는 값보다 작으면 그 밑으로는 더 작은 값들밖에 없기 때문에 더 이상 값을 찾을 수 없으므로 0을 반환한다.

- 서브트리의 왼쪽과 오른쪽 노드에 find 연산을 수행하고 둘 중 큰 값을 반환한다.

값을 찾을 수 없는 경우 0을 반환하기 때문에 둘 중 큰 값을 반환하는 것이다.

 

 

 

 

 

 

 

3. 힙 정렬

- 하나의 요소를 힙에 삽입하거나 삭제할 때 시간이 O(logN)만큼 소요된다. 요소의 개수가 n개이므로 전체적으로 O(nlogN) 시간이 걸린다. (빠른 편)

- 힙 정렬이 최대로 유용한 경우는 가장 큰 값 몇 개만 필요할 때이다.