[Basic C++] #69_priority_queue

2023. 6. 22. 17:02· 언어/Basic C++
목차
  1.  
  2. [Basic C++] #69_priority_queue

 

[Basic C++] #69_priority_queue

 

C++의 STL에서 제공하는 priority_queue컨테이너에 대해 알아보겠습니다.

 


 

Overview

 

  1. 개념
  2. 선언
  3. 멤버 함수
  4. 예제

 

#0. 개념

1. 우선순위 큐?

 

[자료구조]#7_우선순위 큐

[자료구조]#7_우선순위 큐 우선순위 큐 자료구조에 대해 알아보겠습니다. Overview 개념 구현 참고 #0. 개념 1. 우선순위 큐 정의 : 우선순위 큐(Priority Queue)는 원소들이 우선순위에 따라 정렬된 연결

webddevys.tistory.com

 

  • 우선순위 큐는 각 원소에 우선순위를 할당하여, 가장 높은 우선순위를 갖는 원소가 다른 원소보다 먼저 처리되는 자료구조입니다.
  • 우선순위 큐는 가장 높은 우선순위를 갖는 원소가 맨 앞에 위치하며, 우선순위 큐의 삭제작업은 우선순위가 가장 높은 원소의 삭제를 의미합니다.
  • 우선순위 큐의 우선순위는 일반적으로 비교 연산자를 사용하여 지정합니다. 
  • 우선순위 큐의 접근 연산은 O(1)의 시간 복잡도를 가지며, 삽입/삭제 연산의 시간 복잡도는 O(log n)입니다.

 

#. 0 선언

1. 헤더

#include <queue>

 

2. 선언 및 초기화

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Compare {
	bool operator()(const int& a, const int& b)
	{
		return a > b;
	}
};

int main()
{
	// #1. 빈 우선순위 큐 선언
	priority_queue<int> pq1;

	// #2. 다른 컨테이너(vector, deque, list)를 활용한 범위 기반 초기화
	vector<int> v = { 1,2,3,4,5 };
	priority_queue<int> pq2(v.begin(), v.end());

	// #3. 다른 컨테이너를 활용한 초기화
	priority_queue<int, vector<int>> pq3;

	// #4. 다른 컨테이너와 함수 객체를 활용한 초기화 - 1
	priority_queue<int, vector<int>, Compare> pq3;

	// #5. 다른 컨테이너와 함수 객체를 활용한 초기화 - 2
	auto Compare2 = [](const int& a, const int& b) {return a < b; };
	priority_queue<int, vector<int>, decltype(Compare2)> pq4;

}

 

#1. 멤버 함수

1. 접근

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{

	vector<int> v = { 1,2,3,4,5 };
	priority_queue<int> pq(v.begin(), v.end());

	// #1. top() : 우선순위 큐의 원소 중 우선순위가 가장 높은 원소
	cout << pq.top(); 

}

 

2. 삽입/삭제

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{

	priority_queue<int> pq;

	// #1. push() : 우선순위 큐에 새로운 원소 삽입
	pq.push(3);
	pq.push(4);
	pq.push(5);
	pq.push(6);

	// #2. pop() : 우선순위 큐의 우선순위가 가장 높은 원소 삭제
	pq.pop();

}

 

3. 그 외 멤버함수

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{

	priority_queue<int> pq;

	pq.push(3);
	pq.push(1);
	pq.push(2);
	pq.push(4);

	// #1. size() : 우선순위 큐에 저장된 원소의 개수
	cout << pq.size() << '\n';

	// #2. empty() : 우선순위 큐가 비어있는지 체크
	if (!pq.empty())
		cout << "Not Empty" << '\n';
	
	// #3. emplace() : 우측 값 삽입
	pq.emplace(6);

	// #4. swap() : 두 우선순위 큐를 서로 교환
	priority_queue<int> pq2;
	pq2.push(4);
	pq2.push(2);
	pq2.push(3);
	pq2.push(6);

	pq.swap(pq2);

}

 

#2. 

1. BOJ_프린터 큐 문제

 

[BOJ알고리즘, C++]#1966_프린터 큐, 우선순위 큐, 큐

[BOJ알고리즘, C++]#1966_프린터 큐 BOJ 알고리즘 문제 풀이, 1966번 문제 프린터 큐 queue컨테이너와 priority_queue 컨테이너를 활용하는 방법에 대해 알아보겠습니다. Overview 문제 풀이 코드 #0. 문제 #1. 풀

webddevys.tistory.com

 

 

 

'언어 > Basic C++' 카테고리의 다른 글

[Basic C++] #71_multiset  (0) 2023.12.15
[Basic C++] #70_decltype  (0) 2023.08.10
[Basic C++] #68_deque  (0) 2023.06.16
[Basic C++] #67_queue  (0) 2023.06.16
[Basic C++] #66_rotate, 배열 회전  (0) 2023.04.03
  1.  
  2. [Basic C++] #69_priority_queue
'언어/Basic C++' 카테고리의 다른 글
  • [Basic C++] #71_multiset
  • [Basic C++] #70_decltype
  • [Basic C++] #68_deque
  • [Basic C++] #67_queue
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 기술 질문
  • BFS
  • Effective C++
  • 트리
  • C++
  • 알고리즘
  • dfs
  • 최단 경로
  • programmers
  • 그래프
  • unreal
  • set
  • Unreal Blueprint
  • BOJ
  • 개발
  • stl
  • DP
  • 디자인 패턴
  • 정렬
  • 우선순위 큐

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[Basic C++] #69_priority_queue
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.