📌 우선순위 큐
✅ 우선순위 큐
= 우선순위를 가진 항목들을 저장하는 큐
- 우선 순위가 높은 데이터가 먼저 나가게 됨
✅ 우선순위 큐 Heap
✔️ heap의 정의
= 부모 노드 A는 자식노드 B보다 크거나 같은 완전이진트리
- key(A) >= key(B) (중복 허용)
✅ 힙 종류
✔️ 최대 힙(max heap)
: 부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전이진트리
- key(부모노드) >= key(자식노드)
- root : 최대값
✔️ 최소 힙(min heap)
: 부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전이진트리
- key(부모노드) <= key(자식노드)
- root : 최소값
✅ 힙 클래스 설계
- Heap Node 클래스
- Max Heap 클래스
* 힙은 개념만 완전이진트리! 구현은 배열로!
📌 삽입 연산 (⭐⭐⭐)
✅ 삽입 연산
✔️ Upheap 알고리즘 (min heap)
= 삽입된 노드에서 루트까지의 경로에 있는 노드들을 비교/교환
힙의 성질을 복원
- 키 k가 부모 노드보다 크거나 같으면 upheap을 종료한다 (최소힙)
- 키 k가 부모 노드보다 작거나 같으면 upheap을 종료한다 (최대힙)
✅ 삽입 연산을 이용한 Heap Tree 생성
ex) 다음 숫자 2,5,6,8,9,3를 순차적으로 읽고 삽입연산의 반복을 통해 최소 힙트리와 최대 힙트리를 구성하세요
⭐ 삽입을 하는 와중에 힙 성질이 중간에 깨지면 바로 Upheap을 해준다!!
📌 삭제 연산
✅ 삭제 연산
- 최대 힙에서의 삭제 --> 항상 루트가 삭제됨
- 가장 큰 키 값을 가진 노드를 삭제하는 것 (우선순위가 가장 높음)- 루트 삭제 후, 힙 성질을 만족하도록 재구성
📢 재구성 방법 : down heap
⭐ 일단 가장 마지막에 있는 노드를 루트 자리로 올리고, 그 이후에 힙 성질을 만족하도록 downheap을 해준다!!
- 최대힙에선 가장 우선순위가 높은 루트 60을 삭제한다
📢 최대힙 삭제 연산
1. 루트 노드 9를 삭제 후, 맨 마지막에 있는 노드 3을 루트 자리에 올린다.
2. 최대힙 성질을 만족할 때 까지 3을 계속 downheap 해준다.
📌 힙 정렬 (⭐⭐)
✅ Heap Sorting
- 힙을 이용한 정렬 : 힙 정렬
✔️ 최소힙의 경우,
- 먼저 정렬해야할 n개의 요소들을 최소힙에 삽입
- 한번에 하나씩 요소를 힙에서 삭제하여 출력하면 됨
⭐ 삭제된 요소들은 오름차순(뒤로 갈수록 커짐)으로 정렬
✔️ 최대힙의 경우,
⭐ 내림차순으로 정렬
- 오름차순으로 정렬하기 위해서 뒤에서부터 나열
📌 우선순위 큐 Container (⭐⭐)
= C++에서 class priority_queue로 이미 구현이 되어 있음, 이미 insert,delete 기능들이 내재되어 있음!!
✅ class priority_queue
✔️ Type
: priority_queue에 저장되는 요소들의 자료형
ex) int타입의 내용을 담을거임
✔️ Container
: 우선순위 큐에서 사용할 컨테이너를 지정
ex) int타입을 벡터라는 컨테이너에 담는다.
✔️ Compare
: 요소들을 정렬하는 기준
최대힙 or 최소힙, 기본값은 less로서 최대힙, greater는 최소힙
- 최대힙(내림차순)을 사용할거면 compare 자리에
less <int> - 최소힙(오름차순)을 사용할거면 compare 자리에
greater <int>
✅ 힙 코드 구현
✔️ 최대힙(default)
priority_queue<int, vector<int>, less<int>> pq;less<int>은 기본값이므로 안 써도 상관X- 값이 클수록 우선순위가 높음 --> 가장 큰 값이 배열의 가장 맨 위에 옴.
- pq.top()을 호출하면 가장 큰 값이 반환됨.
- 내림차순으로 출력이 됨
✔️ 최소힙
priority_queue<int, vector<int>, greater<int>> pq;- 값이 작을수록 우선순위가 높음. 가장 작은 값이 pq.top()에서 반환됨
- 오른차순으로 출력이 됨
✔️ 생성자
- pq; 를 만나면 pq라는 생성자를 호출함.
- 기본 생성자 :
priority_queue();
--> 빈 우선순위 큐를 생성함. - 파라미터O 생성자 :
priority_queue(InputIterator first, InputIterator last);--> 벡터의 시작과 끝을 가리키는 반복자(=InputIterator)❔ 반복자란? (InputIterator는 반복자 타입)
= 배열이나 벡터와 같은 컨테이너의 요소들을 순차적으로 접근할 수 있게 해주는 도구 - ⭐
pq(v.begin(), v.end());
--> v 벡터의 요소들을 기반으로 우선순위 큐를 초기화❔ 우선순위 큐를 초기화
: 벡터의 요소들을 가지고 새로운 우선순위 큐를 만든다 --> 즉, 벡터의 값을 큐에 넣고 우선순위에 맞게 재배치됨.
❔pq(v.begin(), v.end())
: v.begin() ~ v.end() 이 범위를 priority_queue 생성자에 전달하면 벡터의 모든 요소가 우선순위에 복사됨.
📝 정리
= 우선 벡터 v를 준비하고, 그 벡터의 모든 요소를 priority_queue 생성자에 전달하면 큐가 해당 요소들을 정렬하고 우선순위에 맞게 큐를 구성함.
📢 기본생성자 or 파라미터가 있는 생성자 부르는 기준
1. 기본 생성자를 부르는 경우
: 처음에는 아무 데이터가 없는 빈 우선순위 큐를 만들고, 나중에 하나씩 값을 추가할 때 사용함
priority_queue<int, vector<int>, greater<int>> pq();- 큐에 값을 추가할 때는 pq.push(value,추가하고 싶은 값)을 사용해서 값을 차례대로 넣는다
- 초기 데이터가 없을 때 적합
2. 파라미터가 있는 생성자를 부르는 경우
: 이미 준비된 데이터가 있고, 그 데이터를 기반으로 우선순위 큐를 한 번에 초기화할 때 사용함
priority_queue<int, vector<int>, greater<int>> pq(v.begin(), v.end());- 보통 벡터, 배열, 리스트 등 다른 컨테이너에 이미 값이 들어 있을 때, 그 값들을 한 번에 우선순위 큐로 복사해서 정렬하고 싶을 때 쓰는 방식
- 즉, 데이터를 미리 준비해두고 한 번에 큐로 넘길 때 적합
✅ Functions
✔️ size()
: 우선순위 큐의 요소 개수
✔️ top()
: 우선순위 큐의 맨 위, 루트
✔️ pop()
: 우선순위 큐의 맨 위 요소 제거
✔️ push()
: 우선순위 큐에 요소 하나 추가
✔️ empty()
: 우선순위 큐가 비었는지 확인
📌 우선순위 큐 Container 사용 예시
✅ K개의 작은 수 출력
: 주어진 배열에서 1~K번째로 최소값을 찾아서 출력하는 프로그램을 작성
--> 배열 v 가 주어질 때, 1~K번째로 작은 값을 찾아서 출력
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
int N,K;
vector<int> v;
cin >> N;
//N개의 숫자를 읽어서 벡터v에 저장
for(int i = 0 ; i < N ; i++){
int num;
cin >> num;
v.push_back(num);
}
cin >> K;
// N개의 숫자를 우선순위 큐에 저장 (오른차순으로 정렬해야함 --> greater<int>)
priority queue<int, vector<int>, greater<int>> pq(v.begin(), v.end());
for(int i = 0 ; i < k ; i++){
cout << pq.top() << endl;
pq.pop();
}
}
✅ K번째 최대값 출력 (vector O)
: 배열 v가 주어질 때, K번째로 큰 값을 찾아서 출력하기
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
int N,K;
vector<int> v;
cin >> N'
for(int i = 0 ; i < N ; i++){
int numl
cin >> num;
v.push_back(num);
}
cin >> K;
// N개의 숫자를 우선순위큐에 저장(내림차순으로 정렬-->less<int> 사용, 기본값)
priority_queue<int, vector<int>> pq(v.begin(), v.end());
for(int i = 0 ; i < k-1 ; i++){
pq.pop();
}
cout << pq.top() << endl;K번째 값을 출력하기 위해서는, 그 전에 K-1개의 값을 제거해야함!!
⚠️ K 번째 최대값 출력할 때 주의할 점
📢 틀린 코드)
pq.pop();을 할 때마다 pq.top()을 출력for(int i = 0 ; i < K - 1 ; i++){ pq.pop(); cout << pq.top() << endl; }📢 올바른 코드)
pq.pop()이 끝난 후에 한 번만 pq.top()을 출력for (int i = 0; i < K - 1; i++) { pq.pop(); } cout << pq.top() << endl;
✅ K번째 최대값 출력 (vector X)
: vector를 사용하지 않고, 숫자를 읽어서 바로 priority_queue에 추가하는 방법으로 변경하기
⭐ 파라미터가 없는 기본 생성자 사용하기 !!
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
int N,K;
cin >> N;
priority_queue<int,vector<int>> pq; //기본값,less<int>
// N개의 숫자를 읽어서 우선순위 큐에 저장
for(int i = 0 ; i < N ; i++){
int num;
cin >> num;
pq.push(num);
}
cin >> K;
for(int i = 0 ; i < K-1 ; i++) pq.pop();
cout << pq.top() << endl;
}📢 두 코드의 차이점
1. 벡터 --> 우선순위 큐를 이용한 코드
v.push_back(num);
priority_queue<int, vector<int>> pq(v.begin(), v.end());
2. 바로 우선순위 큐를 이용한 코드
v.push(num);
priority_queue<int,vector<int>> pq;
⚠️ push_back(), push()의 차이점
push_back()
: 벡터는 동적 배열이며, 배열의 끝에 요소를 추가할 때는 순서가 중요하지 않으며, 단순히 배열의 마지막에 추가하는 작업이므로
push_back() 함수 사용
- push_back()은 벡터에서만 사용되는 함수, push()은 에러남!!
push()
: 힙은 각 요소가 우선순위에 따라 정렬돼야 하므로, 새로운 요소를 넣을때마다 그 요소가 알맞은 위치에 들어가도록 자동 정렬- push()함수는 단순히 요소를 넣는게 X --> 삽입 후 그 요소를 적절한 위치에 배치해 큐가 항상 우선순위에 맞는 상태를 유지함
- push_back()를 사용하면 에러남!!
