Node를 저장 해두는 자료구조중 하나이다.
pop할때 저장된 노드중에서 우선순위가 가장 높은 노드가 먼저 나온다.
통상적으로 c++ <prority queue>는 heap으로 구현이 되어있다.
STL에서도 역시 힙을 사용한다.
Heap / 힙 힙 은 완전이진트리( complete binary tree ) 기반 자료구조이며, 최댓값 혹은 최솟값 을 빠르게 찾을수 있는 자료구조이다. 부모 자식간의 관계만 중요하며 형제 노드들과는 관계가 없다.
<prority queue> 는 MAX HEAP 디폴트 값이다.
top에는 항상 MAX값이 들어있다.
std::priority_queue<int> pq;
pq.push(3);
pq.push(7);
pq.push(6);
pq.push(3);
pq.push(4);
pq.push(2);
int top = pq.top();
return 0;
Python
복사
최소값을 기준으로 우선순위를 두고싶다면 다음과 같은 명령어를 추가하면된다.
int main()
{
std::priority_queue<int, std::vector<int>
, std::greater<int>> pq;
pq.push(3);
pq.push(7);
pq.push(6);
pq.push(3);
pq.push(4);
pq.push(2);
int top = pq.top();
return 0;
}
Python
복사
원하는 조건을 만들어서 우선순위를 비교할수도 있다.
#pragma once
#include <iostream>
#include <queue>
struct Node
{
int num;
char ch;
};
bool operator<(Node a, Node b)
{
return a.ch < b.ch;
}
int main()
{
std::priority_queue<Node> pq;
pq.push({3, 'H'});
pq.push({7, 'G'});
pq.push({6, 'B'});
pq.push({3, 'D'});
pq.push({4, 'K'});
pq.push({ 2, 'F' });
pq.push({ 2, 'Z' });
//int top = pq.top();
//int a = 10;
//int b = 20;
//a < b;
return 0;
}
Python
복사
