Priority Queue
📢 내부 데이터를 Remove 할 때 우선 순위가 높은 데이터부터 나오는 큐
Priority Queue 내부의 데이터는 각각 우선 순위를 가져요. 큐의 기본 성질인 FIFO는 동일하지만 Remove할 때 우선 순위가 높은 데이터부터 나오게 되요.
🎨 내부 메서드 (C++)
Priority Queue는 queue 라이브러리 내부에 있어요!
헤더에 #include <queue> 를 선언하고
변수 선언을 통해 사용하시면 됩니다.
priority_queue<자료형> 변수명
| 메서드 이름 | 역할 |
|---|---|
| empty | 우선순위 큐 내부가 비어있는지 알려줌 |
| size | 우선순위 큐 크기 반환 |
| top | 우선순위 큐의 가장 위의 요소 반환 |
| push | 우선순위 큐에 요소 삽입 |
| pop | 우선순위 큐에서 요소 제거 |
| swap | 우선순위 큐끼리 내부 요소 교환 |
empty
pqueue.empty();우선순위 큐 내부가 비어있는지 알려줌
size
pqueue.size();우선순위 큐 크기 반환
top
pqueue.top();우선순위 큐의 가장 위의 요소 반환
push
pqueue.push(5);우선순위 큐에 요소 삽입
pop
pqueue.pop();우선순위 큐에서 요소 제거
swap
priority_queue<int> pqueue1, pqueue2;
pqueue1.swap(pqueue2);우선순위 큐끼리 내부 요소 교환
🔎 다른 정렬 방법을 원한다면
만약에 Priority Queue의 우선 순위 매기는 방식을 다르게 하고 싶으시다면 아래와 같이 코드를 수정하면 돼요.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Item {
int price;
int weight;
string name;
Item(int _price = 0, int _weight = 0, string _name = NULL): price(_price), weight(_weight), name(_name) {}
};
//-------------------compare 구조체 선언으로 정렬 방법 수정 가능----------------
struct compare{
bool operator()(Item a, Item b) {
return a.price < b.price;
}
};
//-------------------------------------------------------------------------
int main() {
// 새로운 Priority Queue 선언
priority_queue<Item, vector<Item>, compare> pqueue;
pqueue.push(Item(1000, 100, "APPLE"));
pqueue.push(Item(2000, 150, "PEACH"));
pqueue.push(Item(3000, 120, "MELON"));
cout << pqueue.top().price << endl;
}
위의 예시는 Item이라는 구조체를 정의해서 가격에 우선 순위를 주어서 가장 높은 가격부터 Remove하는 코드예요.
1. compare 구조체 내부를 수정해서 정렬 방법 수정하기
2. priority_queue<자료형, container<자료형>, compare> 변수명 과 같은 형태로 Priority Queue를 선언하기
위의 2가지 방법을 지켜서 코드를 작성하시면 원하는대로 코드가 작동해요.
📋 예제
백준 1715 - 카드 정렬하기
백준 1715 - 해답
백준 1655 - 가운데를 말해요
백준 1655 - 해답
Heap
📢 Binary Tree를 기반으로 하여 우선순위를 바탕으로 데이터를 저장하는 컨테이너
🔉 Heap 특징
Heap-Order Property
Heap-Order Property는 Parent Node의 값은 항상 Child Node보다 작아야(커야)한다 라는 특징이에요. Binary Serach Tree는 Parent Node를 기준으로 Left-Child는 작은 값, Right-Child는 큰 값을 가져야 했던 것과는 달라요.
Complete Binary Tree Property
또 다른 특징인 Complete Binary Tree Property는 이전 포스트에서 말했던 Complete Binary Tree (완전 이진 트리)의 형태를 지녀야 한다는 점이에요.
Priority Queue는 Heap을 기반으로 한다
Priority Queue의 내부는 Heap으로 구현이 되어 있어요! 다른 자료구조가 아니라 왜 Heap을 사용해서 구현을 했을까요?
아래의 시간 복잡도를 보면 알 수 있어요.
위의 그림의 오른쪽 표를 보게되면 List를 기반으로 한 Priority Queue는 값을 Insert하거나 Remove할 때 O(N)만큼의 시간이 소요되는 것을 볼 수 있어요. 하지만 왼쪽 표를 보게 되면 Heap을 기반으로 할 때 O(N)이 O(logN)만큼 줄어드는 것을 확인할 수 있지요. 그래서 Heap을 기반으로 Priority Queue를 구현하게 된답니다.
📋 예제
백준 11286 - 절댓값 힙
백준 11286 - 해답
백준 1927 - 최소 힙
백준 1927 - 해답
