백준 1927 최소 힙

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

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이�

www.acmicpc.net

서론

11279번 문제인 최대 힙을 변형했다.

백준 11279 최대 힙

문제 : https://www.acmicpc.net/problem/11279 서론 최대 힙에 관한 문제라서 최대 힙을 구현해봤다. 시간초과가 발생해서 무한루프를 예상하고 원인을 매우 아주 상당히 오래 찾았으나 cin, cout의 속도로 �

hydroponicglass.tistory.com

구현

최대 힙과 다른점은

힙을 비교하는 영역들의 부등호를 돌려주면 된다.

그리고 힙을 제거할때 마지막 힙을 루트로 올린 후 마지막 힙을 0이 아닌 최대값으로 저장해줘야 힙을 비교할때 0을 최소값으로 인식하는걸 막을 수 있다. (라인32)

// c++
// min heap

#pragma warning (disable:4996)

#include <cstring>
#include <iostream>
#include <cstdio>

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 (q->heap[index] < q->heap[index / 2]) {
		if (index == 1) 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 (q->heap[index * 2] < q->heap[index * 2 + 1]) nextIndex = index * 2;
		else nextIndex = index * 2 + 1;

		if (q->heap[nextIndex] < q->heap[index]) {
			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;
	//memset(q.heap, 0x3f, sizeof(q.heap));
	int n;
	std::cin >> n;
	while (n--) {
		int x;
		//std::cin >> x;
		scanf("%d", &x);
		if (x == 0) { 
			//std::cout << top(&q) << std::endl; 
			printf("%d\n", top(&q));
			pop(&q);
		}
		else push(&q, x);
	}
}