11286번 절댓값 힙

문제링크 : www.acmicpc.net/problem/11286

11286번: 절댓값 힙

---

---

 

버전 1. vector를 이용하여 heap 구현(메모리 : 2800KB   시간 : 984ms)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void del(vector<long> &d) {
	d[1] = d[d.size() - 1];
	d.erase(d.end()-1);
	int now = 1;

	long mini = 0;
	int miniInd = 1;

	
	while (2*now<d.size()) {
		mini = d[2 * now];
		miniInd = 2 * now;
		if (2 * now + 1 < d.size()) {
			if (abs(d[2 * now]) == abs(d[2 * now + 1])) {
				if (d[2 * now] > d[2 * now + 1])  {
					mini = d[2 * now + 1];
					miniInd = 2 * now + 1;
				}
			}
			else if (abs(d[2 * now]) > abs(d[2 * now + 1])) {
				mini = d[2 * now + 1];
				miniInd = 2 * now + 1;
			}
		}
		if (abs(mini) < abs(d[now])) {
			long temp2 = d[now];
			d[now] = mini;
			d[miniInd] = temp2;
			now = miniInd;
		}
		else if (abs(mini) == abs(d[now])) {
			if (mini < d[now]) {
				long temp2 = d[now];
				d[now] = mini;
				d[miniInd] = temp2;
				now = miniInd;
			}
			else break;
		}
		else { break; }
	}
}

void in(vector<long> &list, long a) {
	list.push_back(a);
	int child = list.size() - 1;
	int parent = (int)(child / 2);
	while (child > 1) {
		if (abs(list[parent]) < abs(list[child])) break;
		else if (abs(list[parent]) == abs(list[child])
			&& list[parent] < list[child]) break;
		else {
			long temp = list[child];
			list[child] = list[parent];
			list[parent] = temp;
			child = parent;
			parent /= 2;
		}
	}
}
int main() {
	int T = 0;
	cin >> T;

	vector<long> list;
	list.push_back(0);
	long a = 0;
	while (T--) {
		cin >> a;
		if (a == 0) {
			if (list.size() == 1) {
				cout << "0\n";
			}
			else {
				cout << list[1] << "\n";
				del(list);
			}
		}
		else {
			in(list, a);
		}
	}
	return 0;
}

 

 

버전 2. priority queue로 heap구현(메모리 : 2460KB   시간: 952ms)

#include<iostream>
#include<queue>
#include <algorithm>
using namespace std;

int main() {
	int T = 0;
	cin >> T;

	int a = 0;
	priority_queue<int, vector<int>, greater<int>> positive;
	priority_queue<int, vector<int>, less<int>> negative;
	while (T--) {
		cin >> a;
		if (a == 0) {
			if (positive.empty() && negative.empty()) cout << "0\n";
			else {
				if (negative.empty()) {
					cout << positive.top() << "\n";
					positive.pop();
				}
				else if(positive.empty()) {
					cout << negative.top() << "\n";
					negative.pop();
				}
				else {
					if (abs(negative.top()) < abs(positive.top())) {
						cout << negative.top() << "\n";
						negative.pop();
					}
					else if (abs(negative.top()) == abs(positive.top())) {
						cout << negative.top() << "\n";
						negative.pop();
					}
					else if (abs(negative.top()) > abs(positive.top())) {
						cout << positive.top() << "\n";
						positive.pop();
					}
				}
			}
		}
		else {
			if (a > 0) positive.push(a);
			else  negative.push(a); 
		}
	}
	return 0;
}