TIL (2022.04.05)
Heap
heap은 빠르게 최댓값, 최솟값을 찾아내기 위한 자료구조이며, 완전 이진트리 (complete binary tree)를 기본으로 한다.
max-heap, min-heap을 사용하면 특정 숫자가 추가되고 삭제 되었을 때 -> 최대 최소 구할 시 시간은 O(logn)
max-heap =
루드 노드에는 전체 숫자 중 최댓값이 항상 들어가는 것
-> 삭제는 루트 노드에서만 가능
-> 몇번째 최댓값 구하는 것 불가능
min-heap =
루트 노드에는 전체 숫자 중 최솟값이 항상 들어가는 것
[백준 11279번 최대 힙] c++(https://www.acmicpc.net/problem/11279)
priority_queue를 사용하면 풀 수 있다. 큰 값이 우선순위로 나옴.
#include <iostream>
#include <queue>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
priority_queue<long long> pq;
int n;
cin>>n;
for(int i=0;i<n;i++){
int num;
cin>>num;
if(num==0){
if(pq.empty()){
cout<<0<<'\n';
}else{
int tp=pq.top();
cout<<tp<<'\n';
pq.pop();
}
}else{
pq.push(num);
}
}
return 0;
}
[백준 1927 최소 힙]c++(https://www.acmicpc.net/problem/1927)
priority_queue를 반대로 하면 최소 힙이 된다.
priority_queue<int,vector< int>,greater< int>> pq;
= int 형을 vector에 담고 작은 순서대로
greater 를 위해서 #include < functional > 해야한다.
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
priority_queue<int,vector<int>,greater<int>> pq;
for(int i=0;i<n;i++){
int num;
cin>>num;
if(num==0){
if(pq.empty()){
cout<<0<<'\n';
}else{
cout<<pq.top()<<'\n';
pq.pop();
}
}else{
pq.push(num);
}
}
}
Author And Source
이 문제에 관하여(TIL (2022.04.05)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@suzu11/TIL-2022.04.05-6gpt4gwf저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)