[자료구조] 우선순위 큐(Priority Queue)란?

우선순위 큐(PQ: Priority Queue)란? 

• 기존의 큐는 먼저 들어온 순서대로 First In, First Out (FIFO)을 만족하지만,
  우선순위 큐는 우선순위가 더 높은 원소에 대하여 IO 먼저 진행한다.

 

 

---

 

 

 

우선순위 큐(Priority Queue) 구현은 어떻게 할까?

• 일반적으로 힙(Heap)을 이용한다. (힙이란?)
  • 배열이나 연결리스트를 사용하지 않는 이유는? (찬희님의 블로그)
     → 삽입 과정에서 소요되는 시간이 O(n)으로 비교적 길기 때문에
• 값이 클 수록 우선순위가 높다고 가정했을 경우, 아래와 같이 최대힙을 사용하여 우선순위 큐를 구현해 준다.
• 힙의 성질에 따라,
  • n번째 노드의 자식들은 2n, 2n+1번째에 채워지게 된다.
  • n번째 노드의 부모는 n / 2 번째에 위치한다.
• PQ의 Push == 힙의 Insert
• PQ의 Pop == 힙의 Delete

삽입 (Insert)

삽입이 될 새로운 키를 newKey라고 하자. 

1. 마지막 위치에 newKey를 채워준다.
2. newKey < 부모 Key 일 경우, 부모와 key 값을 교체한다.
3. Root까지 2번 작업을 반복한다.

void insert(int newKey) {
	heap[++heapSize] = newKey;
    
    for (int i = heapSize; i > 1; i /= 2) {
    	if (heap[i / 2] > heap[i]) {
        	swap(i / 2, i);
        }
        else {
        	break;
        }
    }
}

 

 

삭제 (Delete)

 Heap에서의 삭제는 Root 삭제를 의미한다.

1. Root 삭제한다.
2. 가장 마지막 Key를 Root로 옮겨준다.
3. Key > 자식 Key 일 경우, 자식 중 더 작은 자식과 교체한다.
4. 3번 작업을 반복하여 더 이상 큰 자식이 없을 경우 작업을 마친다.

int delete() {
	if (heapSize == 0) return 0;
    
    int rootKey = heap[1];
    heap[1] = heap[heapSize--];
    
    for (int i = 1; 2 * i <= heapSize) {
    	int leftChild = 2 * i;
    	int rightChild = 2 * i + 1;
    
    	if (heap[i] < heap[leftChild] && heap[i] < heap[rightChild]) break;
        
        if (heap[leftChild] < heap[rightChild]) {
        	swap(i, rightChild);
            i = rightChild;
        } 
        else {
        	swap(i, leftChild);
            i = leftChild;
        }
    }
    
    return rootKey;
}

 

 

https://chanhuiseok.github.io/posts/ds-4/

index	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
priority	-	13	5	8	2	1	6	4

 

 

 

 

 

Reference

• https://chanhuiseok.github.io/posts/ds-4/