우선순위 큐

우선순위 큐는 기존의 큐에 우선순위의 개념을 도입한 자료구조로, 우선순위를 어떻게 하느냐에 따라 우선순위 큐는 스택이나 큐처럼 동작할 수도 있다

 

우선순위 큐는 배열, 연결 리스트, 힙 등의 방법으로 구현이 가능하다

 

1. 배열

• 비정렬 배열
   - 삽입 : 배열의 맨 끝에 새 요소 추가 / O(1)
   - 삭제 : 배열 내에서 우선 순위가 높은 요소를 찾고 해당 요소를 삭제 / O(n)
   - 삭제 후 빈 자리를 메우기 위해 앞으로 이동
• 정렬 배열
   - 삽입 : 이진탐색이나 순차탐색 등을 활용하여 삽입 위치를 파악 후, 해당 위치 뒤의 요소들을 뒤로 이동시키고 새 요소 추가 / O(n)
   - 삭제 : 정리된 배열 내의 맨 앞이나 맨 뒤의 요소를 삭제

2. 연결 리스트

• 비정렬 연결 리스트
   - 삽입 : 첫 번째 노드로 삽입 / O(1)
   - 삭제 : 리스트 내 모든 노드를 탐색 후 해당 노드를 삭제 / O(n)
• 정렬 연결 리스트 (우선 순위가 높은 노드가 맨 앞)
   - 삽입 : 리스트를 탐색해서 삽입 위치를 찾고 해당 위치에 노드 삽입 / O(n)
   - 삭제 : 첫 번째 노드 삭제 / O(1)

3. 힙 (Heap)

 - 완전 이진 트리의 일종, 우선순위 큐를 위해 특별히 만들어진 자료 구조 

 - 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어짐

 

• Max Heap : 부모 노드의 키 값이 자식 노드보다 큼
• Min Heap : 부모 노드의 키 값이 자식 노드보다 작음

 

Max Heap

 - 힙은 배열로 표현 가능 -> 부모의 인덱스를 통해 자식 인덱스를 알 수 있음 (반대도 마찬가지)

 - 구현을 위해 0번 인덱스는 사용하지 않음

 

 정의

// Heap 정의
#define MAX = 200
typedef struct
{
    int heap[MAX];
    int heap_size = 0;
} Heap;

 

 

 삽입

 - 새 노드를 힙의 마지막에 삽입 -> 삽입한 노드를 부모 노드들과 교환하며 힙 성질을 만족시킴

// 새 노드 추가
void HeapAdd(Heap* h, int key)
{
    h -> heap[++(h -> size)] = key;
    HeapUp(h);
}

// 힙 정비
void HeapUp(Heap* h)
{
    if (h -> size > 1)
    {
        int p = ⌊h -> size / 2⌋;
        if (h -> heap[h -> size] > h -> heap[p])
        {
            int temp = h -> heap[p];
            h -> heap[p] = h -> heap[h -> size];
            h -> heap[h -> size] = temp;
            
            // 재귀
            HeapUp(h);
        }
    }
}

삽입

삭제

 - 루트 노드 삭제 -> 마지막 노드를 루트 노드 위치로 이동 -> 힙 재정비

// 루트 노드 삭제
int HeapDelete(Heap* h)
{
    // 루트 노드 저장
    int item = h -> heap[1];
    
    // 마지막 노드를 루트로 이동
    h -> heap[1] = h -> heap[(h -> size)--];
    
    // 힙 재정비
    HeapDown(1, h);
    
    return item;
}

void HeapDown(int root, Heap* h)
{
    if (root <=  ⌊h -> size / 2⌋)
    {
        int l = 2 * root;
        int r = (2 * root) + 1;
        
        // root와 자식 노드들 중 가장 큰 값을 지닌 인덱스
        int m = Max(h -> heap[root], h -> heap[left], h -> heap[right])
        
        if (root != m)
        {
            // 힙 재정비
            int temp = h -> heap[m];
            h -> heap[m] = h -> heap[root];
            h -> heap[root] = temp;
            
            // 재귀
            HeapDown(m, h);
        }
    }
}

삭제

힙 정렬 - 힙 구성 (Heap Building)

• 하향식 (Top-Down) : 힙에 순차적으로 데이터를 삽입하는 방법과 유사 / \(O\)(n\(\log n\))
• 상향식 (Bottom-Up) : 삽입 순서대로 트리 먼저 생성 -> 힙 재정비 / \(O\)(n)