[알고리즘 공부 16차]

1. 최대힙

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	priority_queue<int> p;
	int cnt;
	cin >> cnt;
	while (cnt--)
	{
		int num;
		cin >> num;
		if (num == 0)
		{
			if (p.empty())
				cout << '0' << '\n';
			else
			{
				cout << p.top() << '\n';
				p.pop();
			}
		}
		else
		{
			p.push(num);
		}
	}
	return 0;
}

c++내에서 제공하는 우선순위큐 STL을 사용하면 쉽게 해결할수있다 우선순위큐는 자동으로 큐를 내림차순으로 정렬하며 데이터를 저장한다 즉 문제에서 요구하는 최대힙을 구현할수있음으로 0이입력되었을경우 큐가 비어있다면 0을 아니라면 top을 통해 가장위에 있는 인자를 출력해주면된다.

2.최소힙

#include <iostream>
#include <queue>
#include <functional>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	priority_queue<int,vector<int>,greater<int> > p;
	int cnt;
	cin >> cnt;
	while (cnt--)
	{
		int num;
		cin >> num;
		if (num == 0)
		{
			if (p.empty())
				cout << '0' << '\n';
			else
			{
				cout << p.top() << '\n';
				p.pop();
			}
		}
		else
		{
			p.push(num);
		}
	}
	return 0;
}

1번과 반대로 최소힙을 구현해야하는문제 마찬가지로 c++에서 제공하는 STL을 통해 쉽게 해결할수있다 최소힙을 구현하는 방법은 우선순위큐는 기본적으로 top부터 내림차순으로 정렬이된다 이를 반대로 오름차순으로 하기위해선 우선순위큐를 선언할때 priority_queue<int,vector,greater > p 에서 정렬의 비교방식을 바꿔주기 위해 greater로 해주면된다.

3.절댓값 힙

#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

typedef pair<int, int > pi;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int N, num;
	priority_queue<pi, vector <pi>, greater<pi>> q;

	cin >> N;
	while (N--)
	{
		cin >> num;
		if (num == 0)
		{
			if (!q.empty())
			{
				cout << q.top().second << '\n';
				q.pop();
			}
			else
				cout << "0\n";
		}
		else
		{
			q.push(make_pair(abs(num), num));
		}
	}
	return 0;
}

절댓값순으로 오름차순의 우선순위 큐를 구현하는 문제이다 이전문제에 우선순위에서 큐의 데이터를 pair로 저장해주면된다 pair는 int형으로 짝을 이루며 first에는 절대값이 second는 원본값이 들어간다 2번문제와같이 비교식을 greater로 지정해주면 top에서부터 오름차순으로 정렬이되며 데이터가 들어갈것이고 우선 절대값을 비교한뒤 같다면 원본값을 비교하는 순으로 갈것이다 문제에서 같은 절대값일 경우 원본값이 작은경우 즉 -일때를 우선으로 오름차순 결정하기 때문에그것도 해결이된다 입력값으로 0이 들어왔을때 만약 큐가 비어있지안핟면 q.top().second를 통해 원본값을 출력하고 인자를 팝한다 비어있다면 "0\n"을 출력한다 push할때는 입력받은 num을
make_pair(abs(num), num)을 통해 pair로 만들어 푸쉬해준다

4.가운데를 말해요

#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

priority_queue<int, vector<int>, greater<int>> min_heap;
priority_queue<int, vector<int>, less<int>> max_heap;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int N, num;
	cin >> N;
	while (N--)
	{
		cin >> num;

		if (max_heap.empty())
		{
			max_heap.push(num);
		}
		else if (max_heap.size() == min_heap.size())
		{
			max_heap.push(num);
		}
		else
		{
			min_heap.push(num);
		}

		if (!max_heap.empty() && !min_heap.empty() && max_heap.top() > min_heap.top())
		{
			int max_temp = max_heap.top();

			int min_temp = min_heap.top();

			max_heap.pop();
			min_heap.pop();

			max_heap.push(min_temp);
			min_heap.push(max_temp);
		}
		cout << max_heap.top() << '\n';
	}
}

이문제는 완전 이진트리인 최대힙과 최소힙을 통해 해결할수있다 문제를 해결하기위해 top부터 오름차순으로 정렬된 최소힙과 내림차순으로 정렬된 최대힙이 필요하다

두개의 힙에 규칙에 따라 데이터를 넣어준다
1. 최대힙의 크기는 최소힙의 크기와 같거나 1크다
2. 최대힙의 top은 최소힙의 top과 같거나 작다

이규칙에따라 데이터를 최대힙 최소힙에 넣어주면 최대힙의 top값이 배열의 중간값이된다
그이유는 최대힙은 최대에서부터하나씩넣을것이고 최소힙은 왼쪽에서부터 하나넣었을때 문제에서 더 작은값을 출력하라고했음으로 최대힙이 1 더큼으로 그 top값이 두 배열을 합쳤을때의 중간값이 되기 때문이다.
위두 규칙을 알고리즘을 만들어 큐에 적용하면 문제를 해결할수있다.