백준 11286 절댓값 힙

문제 : https://www.acmicpc.net/problem/11286

 

서론

1927 최소 힙 문제에서 힙 교환 조건을 크기에서 절댓값과 크기로 변경 

1927 : https://hydroponicglass.tistory.com/54

 

---

구현

// c++
// min heap

#pragma warning (disable:4996)

#include <iostream>
#include <cstdio>
#include <algorithm>

typedef struct pq {
	int heap[100003] = { 0, };
	int index = 0;
}pq;

void push(pq *q, int item) {
	q->index++;
	q->heap[q->index] = item;

	int index = q->index;
	while (abs(q->heap[index]) <= abs(q->heap[index / 2])) {
		if (index == 1) break;
		if (abs(q->heap[index]) == abs(q->heap[index / 2]) && q->heap[index] > q->heap[index / 2]) break;
		int tmp = q->heap[index];
		q->heap[index] = q->heap[index / 2];
		q->heap[index / 2] = tmp;
		index /= 2;
	}
}

void pop(pq *q) {
	if (q->index == 0) return;
	q->heap[1] = q->heap[q->index];
	q->heap[q->index] = 0x3f3f3f3f;
	q->index--;

	int index = 1;
	while (index * 2 <= q->index) {
		int nextIndex = 0;
		if (abs(q->heap[index * 2]) < abs(q->heap[index * 2 + 1])) nextIndex = index * 2;
		else if (abs(q->heap[index * 2]) == abs(q->heap[index * 2 + 1])) {
			if (q->heap[index * 2] < q->heap[index * 2 + 1]) nextIndex = index * 2;
			else nextIndex = index * 2 + 1;
		}
		else nextIndex = index * 2 + 1;

		if (abs(q->heap[nextIndex]) <= (abs(q->heap[index]))) {
			if (abs(q->heap[nextIndex]) == (abs(q->heap[index])) && q->heap[nextIndex] > q->heap[index]) break;
			int tmp = q->heap[index];
			q->heap[index] = q->heap[nextIndex];
			q->heap[nextIndex] = tmp;
			index = nextIndex;
		}
		else break;
	}
		
}

int top(pq *q) {
	if (q->index == 0) return 0;
	else return q->heap[1];
}


int main() {
	pq q;
	int n;
	std::cin >> n;
	while (n--) {
		int x;
		scanf("%d", &x);
		if (x == 0) { 
			printf("%d\n", top(&q));
			pop(&q);
		}
		else push(&q, x);
	}
}