모든 사진 자료에 관한 출처는 아래 알튜비튜 - 튜터링에 있음을 밝힙니다.
https://github.com/Altu-Bitu/Notice
🎯우선순위큐
- 우선순위가 높은 데이터가 먼저나옴
- 자료의 Root 노드(맨위꼭대기)에서만 모든 연산이 이루어짐
- 모든 연산에 대한 시간 복잡도는 O(log n)
- Heap으로 구현
- 힙의 조건
1.완전 이진트리
2.상위노드의 값은 모든 하위노드의 값보다 우선순위가 크거나 같다.
🚩 Heap 과 BST의 차이
1.방향관계
: Heap은 상하관계이지만 BST는 좌우관계
2.중복
: Heap은 중복이 가능하고 완전트리이지만 BST는 중복이 불가능하고 *완전 이진트리일 필요 없음.
*완전이진트리란?
- 마지막 레벨을 제외하고 모든 레벨을 다채움
- 마지막 레벨의 모든 노드는 왼쪽부터 빈 공간 없이 채움
📥최대힙에서 데이터삽입
:삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태
KEY=10일경우
📤최대힙에서 데이터삭제
:상단의 데이터 삭제시, 가장 최하단부에 있는 노드(가장 맨 마지막에 추가한 노드)를 root 노드로 이동시킨다. root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복한다.(swap)
🎫배열로 힙 구현하기
: 부모 노드 인덱스 = 자식 노드 인덱스 번호 / 2
왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 번호 * 2
오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 번호 * 2 + 1
ex. 부모노드 인덱스가 1일때 왼쪽 자식노드 인덱스는 12, 오른쪽 자식노드 인덱스는 1*2+1
# 🔬코드구현
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> heap_vec;
//empty
bool empty() {
return heap_vec.size() == 1; //index 0은 항상 채워져 있는 상태.
}
//push
void push(int num) {
int idx = heap_vec.size(); //이번에 push할 데이터의 인덱스
heap_vec.push_back(num); //완전이진트리가 되도록 차례대로 채워나감.
//부모노드로 거슬러 올라가며,상위노드와 교환해가면서 적절한 위치를 찾음. 최대힙이므로 부모노드값보다 작아야함.
//그러나 부모노드보다 값이 크면 자리를 swap해줌.그러다가 이제 더이상 값이 크지 않거나 root=1에 도달하면 적정위치를 찾은것.
for (int i = idx ; i > 1; i /= 2) {
if (heap_vec[i] > heap_vec[i / 2]) //자식 노드 값이 더크다면
swap(heap_vec[i], heap_vec[i / 2]); //부모노드와 자리 교환
else break;
}
}
//pop
int pop() {
int max = heap_vec[1]; //현재 우선순위큐에서 가장 큰 값은 root에 저장.
//vector 는 pop_front하는 기능이 없기 때문에 일단 자리를 바꾸고 팝해주는 방식으로 root노드를 제거해주어야함.
int idx = heap_vec.size(); //맨 마지막 데이터의 인덱스
swap(heap_vec[1] , heap_vec[idx-1]); //맨마지막 <-> root값 교환
heap_vec.pop_back();
//root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복
int parent = 1, child = 2;
//아래로 내려가면서 자리교환
while (child<heap_vec.size())
{
if (child + 1 < heap_vec.size() && heap_vec[child + 1] > heap_vec[child]) //오른쪽 노드가 존재하고, 왼쪽 노드보다 크다면
child++; //오른쪽 노드값 갱신
//즉, child에는 왼쪽,오른쪽 노드중 더 큰 값의 인덱스가 담김.
if (heap_vec[child] <= heap_vec[parent]) //만일 부모노드가 더 크다면
break; // 그곳이 적정위치이므로 반복문을 빠져나감 (더이상 교환이 일어나지 X)
swap(heap_vec[parent], heap_vec[child]);// 자식노드와 부모노드 값 교환.
parent = child; //현재 자식을 부모로 초기화
child = parent * 2; //초기화된 부모의 자식 인덱스 설정(왼쪽 노드) child인덱스를 왼쪽 노드로 초기화.
}
return max;
}
int main() {
//입출력 속도 향상
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, x;
heap_vec.push_back(0); //인덱스가 1부터 시작하도록
cin >> n;
while (n--) {
cin >> x;
if (x == 0) {
if (empty())
cout << 0 << '\n';
else {
cout << pop() << '\n';
}
}
else
push(x);
}
}🔑마무리
- 우선순위 큐는
힙으로 구현하고 시간복잡도가O(log n)인 자료구조 - 효율성을 보는 문제에 주로 사용됨.
그리디,최단경로 알고리즘풀이에 활용되기도함.- cmp정의할때는 헷갈리지 말기. 우선순위큐는 comp가 true를 반환해야 swap됨.
- 무한루프(pop을 하지 않음), 런타임에러(empty체크 안하고 조회or삭제 시도) 조심!!
❓이것도 알아보세요
- 힙을 배열로 구현할때 인덱스를 1부터 시작한 이유가 무엇일까요?
0부터 시작한다면 어떻게 될까요?
: 원래는 자식/2하면 부모노드가 나왔는데 0부터 배열을 시작하게 되면 자식/2하면 왼쪽노드와 오른쪽노드의 부모노드값이 다르게 나와서 계산이 까다로워짐.
ex) 0의 자식노드 ->1,2 1의 자식노드 ->3,4
1/2=0(왼쪽노드) 지만 2/2=1 (오른쪽 노드) 즉 0!=1인 상황 발생.
즉 계산을 보다 더 편리하게 위해서 index를 1부터 시작한 것.
⚜🔰🔬🔭▶➡
✒📤🧾📜📗📕📘💡💾⛏🛠🔑🔏🔊🌈🔥🚩💫❓❗🔰♻✅✔🟥🟧🟨🟩🟦🟪🔺🖼🎞🎨🎗🔑⚠❔🔀↪➰💱🔴🔴🟠🟡🟢🔵🟣🟤⚫🗨🗝🔑🔨🔐🛠🎬🕯📸🔖👾👻✔👑💎🧨🎯🔍📥🎫📲💻💿📹
