[C++/자료구조] 우선순위 큐(Priority Queue)

우선순위 큐 ?

C++의 표준 라이브러리(Library)에서 제공되는 priority_queue 는 우선순위 큐 자료구조를 구현한 클래스 입니다.

 

우선순위 큐는 데이터를 삽입과 동시에 자동으로 정렬이되고 정해진 기준에서 가장 높은 우선순위를 가진 요소가 항상 상단에 위치하도록 유지 합니다.

 

priority_queue 를 사용하기 위해서는 <queue> 헤더 파일의 선언이 필요합니다.

https://www.fluentcpp.com/2018/03/20/heaps-and-priority-queues-in-c-part-3-queues-and-priority-queues/

---

1. 우선순위 큐의 기본 동작 및 특성

1. 정렬 순서는 기본 내림 차순으로 가장 큰 값이 상단에 위치합니다.

2. 요소의 삽입, 삭제가 이루어 질때마다 자동으로 정렬을 실행합니다.

3. 힙(heap) 자료구조를 기반으로 구현되어 효율적으로 작동합니다.

*힙(heap) 자료구조 복습하기(아래 접은글)

힙(heap)

힙은 특정한 규칙을 가지는 완전이진트리(Complete Binary Tree)의 일종입니다.

최댓값 또는 최솟값을 빠르게 찾아내는 연산을 지원합니다.

주로 우선순위 큐와 같은 우선순위 기반의 자료구조를 구현하는데 사용됩니다.

 

힙의 특징

1. 최대 힙 - 가장 큰 값이 루트노드이며 부모 노드의 값이 자식노드보다 항상 큽니다.

2. 최소 힙 - 가장 작은 값이 루트노드이며 부모 노드의 값이 자식노드보다 항상 작습니다.

 

힙의 연산

insert(item)

요소(item)를 힙에 삽입합니다. 힙의 규칙을 유지하며 적절한 위치로 재배치됩니다.

 

deleteMax() & deleteMin()

최대 힙에서는 루트 노드를 삭제하고, 최소 힙에서는 루트 노드를 삭제합니다.

삭제 후 힙의 규칙을 유지하기 위해 마지막 노드가 루트로 이동하며 다시 정렬됩니다.

 

findMax() & findMin()

최대 힙에서는 루트 노드의 값을 반환하고, 최소 힙에서는 루트노드의 값을 반환합니다.

이 값은 힙에서 가장 큰 값 또는 가장 작은 값입니다.

 

heapify()

주어진 배열을 힙으로 변환합니다. 이 과정은 배열의 요소를 하나씩 삽입하면서 힙 규칙을 유지하며 정렬하는 과정입니다.

 

정리

힙은 삽입과 삭제의 연산이 O(log n)의 시간 복잡도를 가지기 때문에 대용량 데이터에서 최대값이나 최소값을 효율적으로 찾아낼 수 있습니다. 이러한 특징으로 인해 유선순위 큐와 같은 응용에서 널리 사용됩니다.

 

---

2. 생성자

priority_queue<(1)Type, (2)Container, (3)Compare>

(1)Type

타입은 저장될 요소의 데이터 타입입니다. (ex. int float, double ... class... 자료형)

(2)Container

컨테이너는 내부적으로 사용할 컨테이너의 타입 입니다. (기본값은 std::vector)

(3)Compare

우선순위를 비교하기 위한 비교 함수 객체 입니다. (기본값은 내림차순 정렬의 less)

---

3. 주요 멤버 함수 및 연산

push(value) : 새로운요소(value)를 삽입 합니다.

pop() : 가장 우선순위(Comapare 조건에서)가 높은 요소를 제거 합니다.

top() : 가장 우선순위(Comapare 조건에서)가 높은 요소에 접근 합니다.

empty() : 우선순위 큐가 비어있는지 여부를 반환 합니다.(비어있다면 true(1), 비어있지않다면 false(0))

*empty()의 사용 예제참조 (아래 접은글)

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    if (pq.empty()) {
        std::cout << "Priority queue is empty." << std::endl;
    } else {
        std::cout << "Priority queue is not empty." << std::endl;
    }

    pq.push(5);

    if (pq.empty()) {
        std::cout << "Priority queue is empty." << std::endl;
    } else {
        std::cout << "Priority queue is not empty." << std::endl;
    }

    return 0;
}

size() : 우선순위 큐에 저장된 요소의 갯수를 반환합니다.

---

4. 우선순위 큐 사용 예제

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	priority_queue<int, vector<int>, greater<int>> MinHeap;
    
    // 우선순위 큐에 int형 요소를 무작위 삽입
    MinHeap.push(10);
    MinHeap.push(5);
    MinHeap.push(20);
    MinHeap.push(3);
    MinHeap.push(15);
    
    cout << "MinHeap의 요소 : ";
    
    while(!MinHeap.empty()) // MinHeap의 요소가 없어질때까지 반복
    {
    	cout << MinHeap.top() << " "; // top 요소를 출력하고
        MinHeap.pop(); // top 요소를 제거
    }

	return 0;
}

출력 결과

MinHeap의 요소 : 3 5 10 15 20 

 

위의 예제 코드는 우선순위큐 MinHeap 객체를 생성하여 작은 값의 순서대로 출력시키는 예제입니다.

우선순위 큐의 타입은 int 형 이며, 최소값을 빠르게 찾기위하여 Compare는 greater<int> 비교함수 객체를 사용하였습니다.