우선순위 큐의 개념과 구현, 힙의 구현과 응용; 힙정렬

우선순위 큐(priority queue) 

->  우선순위를 가진 원소들을 저장하는 큐. 들어온 순서에 상관없이 가장 우선순위가 높은 항목이 삭제됨. 스택이나 FIFO 큐도 우선순위 큐의 특별한 형태라고 볼 수 있음. 최소(min) 우선순위 큐와 최대(max) 우선순위 큐 존재.

 

 

 

▷ ADT

create() :: = 우선순위 큐를 생성

init(pq) :: = 우선순위 큐 pq를 초기화

is_empty(pq) :: = 우선순위 큐 pq가 비어있는지 검사

is_full(pq) :: = 우선순위 큐 pq가 가득 찼는지 검사

insert(pq, x) :: = 우선순위 큐 pq에 원소 x를 추가 (x값을 우선순위라고 가정)

deleteMin(pq) :: = 우선순위 큐 pq로부터 가장 우선순위가 높은 원소를 삭제하고 반환. 최대 우선순위 큐에선 deleteMax

peep(pq) :: =  우선순위가 가장 높은 원소를 반환

 

 

 

▷ 구현

 

○  배열, 연결리스트

: hyunah-home.tistory.com/entry/%ED%81%90%EC%9D%98-%EA%B5%AC%ED%98%84%EA%B3%BC-%EC%9D%91%EC%9A%A9-%EB%8D%B1deque

큐의 구현과 응용; 덱(deque)

위의 글을 참고. 정렬 되었든 안 되었든 배열과 연결 리스트는 삽입이나 삭제 둘 중 하나는 반드시 선형시간의 시간복잡도를 가짐. 

 

 

○  힙(heap)

: 힙으로 구현하면 삽입과 삭제를 logn 시간복잡도로 시행할 수 있음

 

 

 

 

 

 힙(heap)

-> 노드에 저장된 키값들이 특정 조건을 만족하는 완전이진트리. 루트로부터 임의의 단말노드로 어떤 경로를 통해 가든 정렬되어 있음.

 

 

▷ 종류와 성질

 

· 최대 힙(max heap) : 부모 노드의 키값이 자식 노드들의 키값보다 크거나 같은 완전 이진트리. key(부모 노드) >= key(자식 노드). 루트가 최대값.

 

· 최소 힙(min heap) : 부모 노드의 키값이 자식 노드들의 키값보다 작거나 같은 완전 이진트리. key(부모 노드) >= key(자식 노드). 루트가 최소값.

 

· 힙은 완전이진트리이기 때문에 n개의 노드를 가지고 있는 힙의 높이 h는 floor(logn). 즉 마지막 레벨 h를 제외하고는 각 레벨 i에 2ⁱ개의 노드가 존재하고, 마지막 레벨은 노드가 왼쪽부터 오른쪽으로 채워져 있음.

 

 

 

▷ 구현

 

: 배열을 이용해 구현. 완전이진트리이므로 각 노드에 레벨순위 순서로 번호를 붙이고 이 번호를 배열의 인덱스로 간주.

부모와 자식 노드를 찾기 쉬움.

루트가 1인 경우 - 노드 i의 부모 노드 인덱스 = floor(i/2), (i!=1),  노드 i의 왼쪽 자식노드 인덱스 = 2i, (2i <= n), 노드 i의 오른쪽 자식노드 인덱스= 2i+1, (2i+1 <= n) 

 

typedef struct {
    int key;
} element;

typedef struct {
    element heap[MAX_ELEMENT];
    int heap_size;
} HeapType;

 

 

○  삽입

: 새로운 원소가 들어오면, 일단 힙의 마지막 노드 다음에 삽입한 다음 upheap 연산을 실시.

 

upheap 연산 - 삽입된 노드로부터 루트까지의 경로에 있는 노드들을 새로운 노드의 key와 비교하여 필요한 경우 교환을 실시함으로써 힙의 성질을 만족하도록 함. 새로운 노드의 key가 부모노드보다 작거나 같으면 (maxheap인 경우) 연산 종료. 최악의 경우 새로운 노드가 루트까지 올라가며 연산이 힙의 높이(logn)만큼 시행되므로 upheap 연산의 시간복잡도는 O(logn)

 

void insert_max_heap(HeapType *h, element item) {
    int i;
    i = ++(h->heap_size); //마지막 노드 다음 위치부터
    
    //힙을 거슬러 올라가면서 key값 비교하는 과정
    while ((i != 1) && (item.key > h->heap[i/2].key)) {
        h->heap[i] = h->heap[i/2]; //부모노드의 key값이 더 작은 경우 부모노드의 값을 자식노드로 끌어내림
        i /= 2;
    }
    h->heap[i] = item; //새로운 노드 삽입

 

 

○  삭제

: 최대힙에서의 삭제는 가장 큰 값을, 최소힙에서의 삭제는 가장 작은 값을 가진 노드를 삭제하는 것을 의미함. 즉, 루트값을 삭제해서 반환하는 것. 루트를 삭제한 후 마지막 노드를 루트로 이동시켜 downheap 연산 실시.

 

downheap 연산 - 마지막 노드를 루트로 올린 후 단말노드까지 내려가면서 자식들 중에서 큰 값을 찾고 다시 해당 값과 비교하면서 경로 상에 있는 노드들과 교환해 힙의 성질을 만족시키도록 함. upheap 연산과 마찬가지로, 최악의 경우 루트까지 올라간 노드가 다시 본래의 자리로 돌아오므로 힙의 높이만큼 연산이 시행되어 downheap 연산의 시간복잡도는 O(logn)

 

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

 

 

 

▷ 응용

○  힙 정렬

: 오름차순 정렬을 할 때는 최대 힙을, 내림차순 정렬을 할 때는 최소힙을 사용.

 

1단계 - 정렬해야 할 n개의 원소들을 최대 힙으로 구성.

 

· 온라인 알고리즘(스트리밍 알고리즘) : 연속적인 삽입 연산에 의해 힙을 구성하는 방법. 시간복잡도는 O(nlogn)

· 오프라인 알고리즘 : 이미 힙의 원소정보가 배열에 저장되어 있는 경우, 단말노드를 제외하고 배열의 뒤에서부터 부분      heap으로 만들어 전체를 힙으로 구성함. 시간복잡도는 O(n)

 

2단계 - 루트값과 마지막 원소를 교환한 다음, 마지막 원소를 제외하고 downheap을 반복적으로 수행.

 

void heap_sort(element a[], int n) {
    int i;
    HeapType h;
    
    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);
}