컴공댕이 공부일지
[ 우선순위 큐와 힙 ] 완전 이진 트리, heap의 구현 ( + 백준 11279번 최대힙) 본문
🔎 우선순위 큐란?
기존의 큐는 먼저 넣은 요소가 먼저 나오는 FIFO( first in - first out )이지만,
우선순위 큐는 들어간 순서 상관없이, 우선순위가 높은 데이터가 먼저 나온다 !
(ex.위급한 사람부터 처치하는 응급실)
우선순위 큐는 힙(Heap)이라는 자료구조로 구현하며,
모든 연산에 대한 시간 복잡도가 O(log n)이다.
📖 완전 이진 트리와 힙
🔎 완전 이진 트리 (complete binary tree)
- 이진 트리(자식이 최대 2개인 트리)의 한 종류
- 마지막 레벨 제외하고는 모든 레벨이 다 채워져있어야 함
- 마지막 레벨의 모든 노드는 왼쪽부터 빈공간없이 채움
📍 힙(Heap)의 조건
1) 완전 이진 트리
2) 힙은 상위노드가 모든 하위노드보다 우선순위가 크거나 같다
최소 최댓값을 찾을 때, 배열을 사용하면 O(n)의 시간복잡도가 걸리고, 배열은 삽입 삭제 연산이 O(n)까지도 걸리지만,
힙을 사용하면 O (1) 시간에 찾을 수 있고, 모든 연산에 대해 O(log n) 시간이 걸린다 !
📚 힙의 삽입 & 삭제 연산
최대 힙을 기준으로 힙의 연산을 살펴보자.
➕ 삽입 연산
맨 마지막 자리에 일단 추가 - 부모자식 비교하며 자리 찾기
➖ 삭제 연산
최대 힙(max heap) 기준, 삭제 연산은 최댓값을 가진 요소를 삭제하는 것
루트 노드 삭제 - 맨마지막 노드를 루트로 - 자식들 중 큰 것과 차차 비교하며 자리 찾기
📝 예시 문제로 알아보는 최대 힙의 구현
1) 배열과 2) 라이브러리 두 가지 방법으로 최대 힙을 구현해보쟈 ! :)
백준 11279번 최대 힙
https://www.acmicpc.net/problem/11279
11279번: 최대 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
1. 배열(vector)로 최대 힙 구현
1. 구현을 쉽게 하기 위해서 인덱스 1부터 시작한다.
2. 인덱스
- 왼쪽 자식 인덱스 : (부모의 인덱스) * 2
- 오른쪽 자식 인덱스 : (부모의 인덱스) * 2 + 1
- 부모 인덱스 : (자식의 인덱스) / 2
#include <iostream>
#include <vector>
using namespace std;
// 힙 비어있는지 체크하는 함수
bool isEmpty(const vector<int>& q) { //벡터에 담긴게 처음 담아준 0밖에 없다면, 텅빈거야 !
return q.size() == 1;
}
// 힙 삭제연산 함수
void pop(vector<int> &q) {
q[1] = q[q.size()-1]; //마지막 노드를 루트 노드에
q.pop_back(); //마지막 노드 삭제
int parent = 1;
int child = 2;
int biggerChild=0; // 더 큰 자식의 인덱스
while(child < q.size()) {
biggerChild = child;
// 오른쪽 자식 노드 존재하고,
if(child<q.size()-1) {
if(q[child] < q[child+1]) { // 오른쪽이 왼쪽보다 크다면,
biggerChild = child+1; // 오른쪽 자식의 인덱스를 biggerChild에 저장
}
}
// 부모가 자식보다 작으면 swqp
if(q[parent] < q[biggerChild]) {
swap(q[parent], q[biggerChild]);
// 새 부모노드 기준으로 인덱스 업데이트
parent = biggerChild;
child = parent*2;
} else { //부모가 크면, break
break;
}
}
}
// 힙 삽입연산 함수
void insert(int x, vector<int> &q) {
q.push_back(x); // x를 마지막 노드에 삽입
int idx = q.size()-1; // x가 들어간 마지막 노드의 인덱스
while(idx > 1) { // 삽입한 노드가 루트가기 전까지 비교 !!!
//부모와 비교
if(q[idx] > q[idx/2]) { // 자식인덱스 / 2 = 부모인덱스
swap(q[idx], q[idx/2]);
idx /=2;
} else { // 부모보다 작다면, 자기 자리 찾은거니깐 ! break
break;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, x;
cin >> n;
// 배열로 최대힙 구현
vector<int> q;
q.push_back(0);
while(n--) {
cin >> x;
if(x) {
// 삽입 연산
insert(x, q);
}
else {
// 삭제 연산
//비어있다면 0 출력
if(isEmpty(q)) {
cout << "0\n";
}
else {
cout << q[1] <<"\n"; // 루트노드 출력
pop(q);
}
}
}
return 0;
}
2. 우선순위 큐 라이브러리 이용
queue 헤더에 있는 우선순위 큐 라이브러리를 사용해서, pop, top, push 함수로 최대 힙 연산을 손 쉽게 처리할 수 있다 !
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, x;
cin >> n;
priority_queue <int> max_heap; // 최대힙으로 우선순위 큐 구현
while(n--) {
cin >> x;
if(x) {
// 삽입
max_heap.push(x);
}
else {
//비어있다면 0 출력
if(max_heap.empty()) {
cout << "0\n";
}
// 삭제
else {
cout << max_heap.top() << "\n";
max_heap.pop();
}
}
}
return 0;
}
'CS > 자료구조' 카테고리의 다른 글
[ 맵과 셋 ] 자료 구조 Map & Set 알아보기 ( + 백준 9375번 패션왕 신해빈 ) (2) | 2024.03.06 |
---|