[C언어 / 백준 - 1927] 최소힙 (우선순위 큐)

www.acmicpc.net/problem/1927

1927번: 최소 힙

우선순위 큐 구현을 할 수 있는지에 대한 문제이다.

별로 설명할 것도 없이 최소힙을 구현하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define MAX_SIZE 100001
#define dep(i,a,b) for(int i=a;i<b;i++)
#define fep(i,a,b) for(int i=a;i<=b;i++)
#define swap(type,x,y) do{type t=x;x=y;y=t;} while(0)
typedef struct heap {
	int size;
	int heap[MAX_SIZE];
}heap;

heap s;

void Init_Heap(heap* p) {
	p->size = 0;
}

int Push(heap* p, int x) {
	if (p->size + 1 > MAX_SIZE) {
		return 0;
	}

	p->heap[p->size] = x;
	int cur = p->size;
	int parent = (p->size - 1) / 2;

	while (cur > 0 && p->heap[cur] < p->heap[parent]) {
		swap(int, p->heap[cur], p->heap[parent]);
		cur = parent;
		parent = (parent - 1) / 2;
	}
	p->size++;

	return 1;
}

int Pop(heap* p) {
	if (p->size <= 0) {
		return 0;
	}

	int cut = p->heap[0];
	p->size--;
	p->heap[0] = p->heap[p->size];

	int cur = 0, minNode = 0;
	int left_child = cur * 2 + 1;
	int right_child = cur * 2 + 2;

	while (left_child < p->size) {
		if (p->heap[left_child] < p->heap[minNode]) {
			minNode = left_child;
		}
		if (right_child < p->size && p->heap[right_child] < p->heap[minNode]) {
			minNode = right_child;
		}
		if (cur == minNode) {
			break;
		}
		else {
			swap(int, p->heap[cur], p->heap[minNode]);
			cur = minNode;
			left_child = cur * 2 + 1;
			right_child = cur * 2 + 2;
		}
	}
	return cut;
}

int main(void) {
	int n;
	scanf("%d", &n);

	Init_Heap(&s);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		if (x == 0)
			printf("%d\n", Pop(&s));
		else
			Push(&s, x);
	}

	return 0;
}