[C언어로 쉽게 풀어쓴 자료구조] 9장 우선순위 큐

9.1 우선순위 큐 추상 데이터 타입

자료구조	삭제되는 요소
스택	가장 최근에 들어온 데이터
큐	가장 먼저 들어온 데이터
우선순위 큐	가장 우선순위가 높은 데이터

 

우선순위 큐는 배열, 연결 리스트 등의 여러가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 히프 heap

 

9.2 우선순위 큐의 구현 방법

배열을 사용하는 방법

*정렬이 되어 있지 않는 경우

- 삽입: 배열의 맨 끝에 새로운 요소 추가 ( 시간 복잡도 : O(1) ) 

- 삭제: 가장 우선 순위가 높은 요소 찾기 (정렬이 안 되어 있으므로 처음부터 끝까지 모든 요소들을 스캔해야함) ( 시간 복잡도 : O(n) ) 

            → 요소가 삭제된 다음, 뒤에 있는 요소들을 앞으로 이동  

 

*정렬이 되어 있는 경우

- 삽입: 다른 요소와 값을 비교하여 적절한 삽입 위치를 결정하여야한다.

           삽입 위치를 찾기 위하여 순차 탐색이나 이진탐색과 같은 방법을 사용 할 수 있다. 

          → 삽입 위치를 찾은 다음에는 삽입 위치 뒤에 있는 요소들을 이동시켜서 빈자리를 만든 다음, 삽입 ( 시간 복잡도 : O(n) ) 

- 삭제: 숫자가 높은 것이 우선 순위가 높다고 가정하면 맨 뒤에 위치한 요소를 삭제 ( 시간 복잡도 : O(1) ) 

          

연결 리스트를 사용하는 방법

*정렬이 되어 있지 않는 경우

- 삽입: 첫 번째 노드로 삽입시키는 것이 유리. 다른 노드를 이동할 필요없음 → 포인터만 변경하면 됨 ( 시간 복잡도 : O(1) ) 

- 삭제: 포인터를 따라서 모든 노드를 뒤져보아야함 ( 시간 복잡도 : O(n) ) 

 

*정렬이 되어 있는 경우

- 삽입: 우선 순위가 높은 요소가 앞에 위치하는 것이 유리

          → 우선순위가 높은 요소가 첫번째 노드가 되도록 함 ( 시간 복잡도 : O(n) ) 

- 삭제: 첫 번째 노드를 삭제 ( 시간 복잡도 : O(1) ) 

 

히프를 사용하는 방법

히프(Heap)는 완전 이진 트리의 일종으로 우선순위 큐를 위해 특별히 만들어진 자료구조

느슨한 정렬 상태를 유지, 히프의 효율은 O(log2n)으로서 다른 방법에 비해 상당히 유리

 

9.3 히프 Heap

부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리

히프트리에서는 중복된 값을 허용 ( *이진 탐색 트리에서는 중복된 값을 허용하지 않음)

 

히프의 종류

히프의 구현

 

 

• 표준적인 자료구조는 배열 ( 배열의 첫번쨰 인덱스인 0은 사용하지 않음)
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음
• 배열을 이용하여 히프를 저장하면 완전 이진 트리에서처럼 자식 노드와 부모 노드를 쉽게 알 수 있음
  • 왼쪽 자식의 인덱스 = (부모의 인텍스) *2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) *2+1
  • 부모의 인덱스 = (자식의 인덱스)/2

9.4 히프 (Heap)의 구현

히프의 정의

#define MAX_ELEMENT 200
typedef struct {
    int key;
} element; // 요소들을 구조체 element로 정의
typedef struct {
    element heap[MAX_ELEMENT];  // elemnet의 1차원 배열을 만들어 히프를 구현
    int heap_size; // 현재 히프 안에 저장된 요소의 개수
} HeapType;

// 위의 정의를 이용하여 히프 Heap를 생성하고 싶으면
HeapType heap;

// 동적으로 생성 -> 메모리 동적 할당을 이용
HeapType *heap = create();

 

삽입 연산

• 신입 사원 승진 과정과 비슷
  • 새로운 노드를 힙의 마지막 노드에 이어서 삽입
  • 삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질 만족 (up-heap)
   

// 9.1 히프트리에서의 삽입 함수

// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입
// 삽입 함수 
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; // 새로운 노드를 삽입
}

 

삭제 연산

• 루트 노드에 있는 원소를 삭제하여 반환
• 삭제 과정
  • 루트 노드를 삭제
  • 마지막 노드를 루트 노드로 이동
  • 노드 교환을 통해 히프 성질 만족: 자식 중 더 큰 값과 교환 (down-heap)
   

/ 9.2 히프트리에서의 삭제 함수
// 삭제 함수
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;
}

 

 

9.5 히프 (Heap) 정렬

히프의 정의

• 1차원 배열에 정렬되지 않은 상태로 저장
• 이 데이터들을 차례대로 최대 히프에 추가하여 히프를 생성
• 한번에 하나씩 요소를 히프에서 꺼내서 배열의 뒤쪽부터 저장하면 됨. → 배열 요소들은 값이 증가되는 순서로 정렬
• 이렇게 히프를 사용하는 정렬 알고리즘을 히프 정렬(heap sort)이라고 함

힙의 응용: 힙 정렬

• 정렬할 원소 n개를 최대 힙에 삽입
• 하나의 요소를 힙에 삭제하여 출력 → 내림차순 정렬
• 최소 힙을 사용하면 오름차순 정렬
• O(nlogn)
• 가장 큰 값 몇개만 필요할 떄 유용

// 9.4 히프 정렬 프로그램
// 우선 순위 큐린 히프를 이용한 정렬
void heap_sort(element a[], int n)
{
    int i;
    HeapType* h;

    h=create();
    init(h);
    for (i=0; i<n; i++){
        insert_max_heap(h,a[i]);
    }
    for (i= (n-1); i >=0; i--){
        a[i] = delete_max_heap(h);
    }
    free(h);
}

 

9.6 머쉰 스케줄링

LPT(longest processing time first)

• 각 작업들을 가장 먼저 사용가능하게 되는 기계에 할당.
• 여기서는 최대히프가 아닌 최소 히프를 사용 ( 최소히프: 모든 기계의 종료시간을 저장)
• 처음에는 어떤 기계도 사용되지 않으므로 모든 기계의 종료시간은 0
• 히프에서 최소의 종료 시간을 가지는 기계를 삭제하여서 작업을 할당
• 선택된 기계의 종료 시간을 업데이트하고 다시 히프에 저장.

LPT(longest processing time first) 알고리즘의 구현

• 기계의 종료시간이 중요 → 종료 시간이 최소인 기계가 항상 선택되기 때문
• 기계의 종료 시간을 최소 히프에 넣고 최소 히프에서 기계를 꺼내서 그 기계에 작업을 할당
• 작업을 할당한 후에 기계의 종료 시간을 작업 시간만큼 증가 시킨 후에 다시 최소 히프에 넣는다

9.7 허프만 코드

허프만 코드 huffman code

• 코딩된 비트열을왼쪽에서 오른쪽으로 조사해 보면 정확히 하나의 코드만 일치하는 코드
• 이진트리를 사용하여 허프만 코드 생성 ( 이런 이진트리를 허프만  코딩 트리라 함)
• 각 문자의 빈도가 알려져 있는 메세지의 내용을 압축하는데 사용 될 수 있음

 

허프만 코드 huffman code 생성

• 빈도수가 가장 작은  2개를 찾는 과정에서 최소 힙을 이용
• n개의 각 문자별 빈도수를 모두 힙에 삽입
• 다음을 (n-1)번 반복
  • 힙에서 노드 두개를 삭제
  • 삭제된 노드 키 값의 합을 힙에 다시 삽입