[백준 1927] 최소 힙

문제 링크

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

1927번: 최소 힙

문제 요구 사항

최소 힙 구현

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

 

1번 풀이

자료 구조 힙에서는 배열로 완전 이진 트리를 구성한다.

자식은 부모/2( 나머지는 부모/2 +1)

삽입 할때 제일 끝에 삽입 후 자기 보다 작은 부모가 나올때 까지 올라간다

 

2번 풀이

pop() 할때는 제일 작은 heap[1]을 빼고 제일 마지막 요소를 heap[1]에 넣어

자기 위치를 찾을 수 있도록 한다.

 

 

*우선순위 큐를 사용하면 쉽게 풀 수 있다.

(우선 순위 큐 : 우선 순위(오름차순, 내림차순)대로 우선 순위가 높은대로 자료 보관하는 큐

 

#include <iostream>

using namespace std;

#define MAX 100001

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
struct mypq {
	int size = 0;
	int heap[MAX];

	void push(int data)
	{
		int idx = ++size;
		while ((idx != 1) && ((data < heap[idx/2])))
		{
			swap(&heap[idx], &heap[idx/2]);
			idx /= 2;
		}
		heap[idx] = data;
	}
	int pop()
	{
		if (size == 0)
			return 0;
		int ret = heap[1];
		heap[1] = heap[size--];
		int parent = 1;
		int child;
		while (true)
		{
			child = parent*2;
			if (child + 1 <= size && heap[child] > heap[child + 1])
				child++;
			if (child > size || heap[child] > heap[parent])	
			{
				break;
			}
			swap(&heap[child], &heap[parent]);
			parent = child;
		}
		return ret;
	}
};
int main()
{
	int n;
	scanf("%d", &n);
	mypq q;
	for (int i = 0; i < n; i++)
	{
		int x;
		scanf("%d", &x);
		if (x == 0)
		{
			printf("%d\n", q.pop());
		}
		else
		{
			q.push(x);
		}
	}
}