9장 우선순위 큐

1. 우선순위 큐(priority queue)

우선순위를 가진 항목들을 저장하는 큐.
FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다.

1.1 우선순위큐 ADT

가장 중요한 연산은 insert와 delete연산이다.
우선순위큐는 2가지로 구분한다
- 최소 우선순위 큐
- 최대 우선순위 큐

1.2 히프(heap)란?

노드의 키들이 다음 식을 만족하는 완전 이진트리

최대 히프: key(부모노드) >= key(자식노드)
최소 히프: key(부모노드) <= key(자식노드)

히프의 높이

n개의 노드를 가지고 있는 히프의 높이는 O(logn)
히프는 완전이진트리 
마지막 레벨을 제외하고, 각 레벨 i에 2^(i-1)개 노드 존재

- 히프의 구현방법

부모 자식 노드 찾기가 쉽다.
왼쪽 자식 인덱스 = 부모 인덱스 * 2
오른쪽 자식 인덱스 = 부모 인덱스 * 2 + 1
부모의 인덱스 = 자식 인덱스 / 2

히프 정의

typedef int element;

typedef struct{
    element heap[N];
    int heapSize;
}HeapType;

히프에서의 삽입

신입 사원이 들어오면 말단 위치에 앉힌 다음 신입 사원의 능력을 봐서 위로 승진시키는 것

[1] 새로운 element를 마지막 노드 다음으로 삽입
[2] element를 부모 노드와 교환하여 성질을 만족

void upHeap(HeapType *H)
{   
    int i = H->heapSize;
    element key = H->heap[i]; //현재 삽입된 마지막 노드

    while(i != 0 && (key > H->heap[i/2]))
    {
        H->heap[i] = H->heap[i/2];
        i /= 2;
    }
    H->heap[i] = key;
} 

void InsertHeap(HeapType *H, int key)
{
    H->heapSize++;
    H->heap[H->heapSize] = key;
    upHeap(H);
}

히프에서의 삭제

최대 히프에서의 삭제는 가장 큰 키값을 가진 노드를 삭제하는 것을 의미 -> 루트 노드 삭제
제일 말단 사원을 사장 자리로 올리고 능력에 따라 강등시키는 것과 비슷하다.

[1] 루트 노드를 삭제한다
[2] 마지막 노드를 루트 노드로 이동한다.
[3] 루트에서 단말 노드까지의 경로에 있는 노드를 교환하여 히프 성질을 만족시킨다.

element removeHeap(HeapType *H)
{
    element key = H->heap[1];
    H->heap[1] = H->heap[H->heapSize--]; 
    downHeap(H);

    return key;
}

void downHeap(HeapType *H)
{
    element key = H->heap[1];
    int parent = 1, child = 2;

    while(child <= H->heapSize)
    {
        if(child < H->heapSize && H->heap[child] < H->heap[child+1])
            child++;
        if(H->heap[child] < key)
            break;
        
        H->heap[parent] = H->heap[child];
        parent = child;
        child *= 2; 

    }

    H->heap[parent] = key;
}

메인 함수

int main(){
    HeapType H;
    init(&H);

    InsertHeap(&H, 9);
    InsertHeap(&H, 7);
    InsertHeap(&H, 6);
    InsertHeap(&H, 5);
    InsertHeap(&H, 4);
    InsertHeap(&H, 3);
    InsertHeap(&H, 2);
    InsertHeap(&H, 2);
    InsertHeap(&H, 1);
    InsertHeap(&H, 3);
    

    print(&H);

    printf("%d delete \n", removeHeap(&H));
    print(&H);

    InsertHeap(&H, 8);
    print(&H);

}

<출력값>
1. [9]   2. [7]   3. [6]   4. [5]   5. [4]   6. [3]   7. [2]   8. [2]   9. [1]   10. [3]   
9 delete
1. [7]   2. [5]   3. [6]   4. [3]   5. [4]   6. [3]   7. [2]   8. [2]   9. [1]
1. [8]   2. [7]   3. [6]   4. [3]   5. [5]   6. [3]   7. [2]   8. [2]   9. [1]   10. [4]

히프의 복잡도 분석

삽입 & 삭제 연산 최악의 경우 트리 높이에 해당하는 이동 -> O(logn)

히프 정렬

<히프를 이용한 정렬>
[1] n개의 요소들을 최대 히프에 삽입.
[2] 한번에 하나씩 요소를 히프에서 삭제하여 저장.
[3] 히프 정렬은 가장 큰 값 몇가지를 구할 때 유용하다.

void heapSort(element a[], int n)
{
    HeapType *H = (HeapType *)malloc(sizeof(HeapType));
    init(H);

    
    for(int i = 0; i < n; i++)
        InsertHeap(H, a[i]);
    for(int i = n-1; i >= 0; i--)
        a[i] = removeHeap(H);
    
    free(H);
}

1.3 LPT 방법

1.4 허프만 코드

이진 트리는 글자의 빈도가 있는 메시지 내용을 압축하는데 사용될 수 있다.