[Baekjoon][#1927] 최소 힙

• [ 장르 ] Heap or ★ Priority_queue
• [ 문제 ]

1927번: 최소 힙

• My Code ( 최소 순차 힙(순차리스트,배열) 구현 ver. )

#include <iostream>
using namespace std;
int arr[100000], n = 0;
 
void insertItem(int data);
int removeMin();
void upHeap(int idx);
void downHeap(int idx);
 
int main()
{
	int N,data;
 
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> N;
	while (N)
	{
		cin >> data;
		if (data != 0)
			insertItem(data);
		else
			if (data == 0 && n == 0)
				cout << 0 << '\n';
			else
				cout << removeMin() << '\n';
		N--;
	}
}
void insertItem(int data)
{
	arr[n + 1] = data;
	upHeap(n + 1);
	n = n + 1;
}
int removeMin()
{
	int removeData = arr[1];
 
	arr[1] = arr[n];
	downHeap(1);
	n = n - 1;
	return removeData;
}
void upHeap(int idx)
{
	int tmp;
	if (idx != 1)
	{
		if (arr[idx / 2] > arr[idx])
		{
			tmp = arr[idx];
			arr[idx] = arr[idx / 2];
			arr[idx / 2] = tmp;
			upHeap(idx / 2);
		}
	}
}
void downHeap(int idx)
{
	int smaller,tmp;
	
	if (n >= idx * 2)
	{
		smaller = idx * 2;
		if (n >= idx * 2 + 1)
			if (arr[smaller] > arr[idx * 2 + 1])
				smaller = idx * 2 + 1;
		if (arr[smaller] < arr[idx])
		{
			tmp = arr[idx];
			arr[idx] = arr[smaller];
			arr[smaller] = tmp;
			downHeap(smaller);
		}
	}
}

• ★ My Code ( Priority_queue < greater > ver. )

#include <iostream>
#include <queue>
 
using namespace std;
 
int main()
{
	int N, data;
	priority_queue<int, vector<int>, greater<int>> pq;		// ★ 내림차순 ( 기본옵션은 
 
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> N;
	while (N)
	{
		cin >> data;
		if (data != 0)
			pq.push(data);
		else
			if (data == 0 && pq.size() == 0)
				cout << 0 << '\n';
			else
			{
				cout << pq.top() << '\n';
				pq.pop();
			}
		N--;
	}
}

 " Priority_queue의 기본 옵션은 내림차순(less<자료형>) 입니다. "

• [ CheckPoint ]

• 먼저, 힙 생성에 대해서, 힙 생성은 1. 삽입식 힙생성, 2.상향식 힙생성이 있다.
  1. 삽입식 힙생성 : 힙에 value에 대한 정보가 순차적으로 제시되는 경우
  2. 상향식 힙생성 : 힙에 value가 한번에 제시되는 경우
• 이 문제는 그 중 삽입식 힙 생성이고, 최대 힙, 최소 힙중에 "최소 힙" 생성이다.
• 참고로, 힙은 순차힙( 배열에 의한 )과 연결 힙( 연결리스트에 의한 )이 있는데, 구현의 편의성을 위해 "순차 힙"으로 구현했다.
  ( 사실, 현재 이 글을 작성하는 시점에서의 힙을 나는 순차힙으로만 구현해 봐서, 순차 힙으로 구현했다..^^;; )
• ver.1 ( 구현한 힙 )은 기본적인 힙 생성 절차이기 때문에 천천히 코드를 읽어보면 이해가 될 것이다.
  
• 포인트는 ver.2 ( Priority_queue )로 구현한 것인데, 중요한 걸 먼저 짚고가면, 정확히 이것은 힙이 아니다 !
  힙에 대한 성질은 내부적으로보면 전혀 맞지 않고, 오로지 이 문제가 "최소 힙"이지만 결론적으로, 출력할 때 힙의 최소값만 출력하면 되는 방식이기 때문에, 내부적으로 어떤지는 중요하지 않다. ( 다시한번, 강조하지만 이 문제에만 초점을 맞췄다. )
• 다음은, 어찌 됬든 Priority_queue를 사용할 것을 알았다면, C++에서 Priority_queue에 대한 사용법을 알아야 한다.
  
• 헤더파일 : include <queue>
  선언시 : priority_queue<자료형, 구현체, 비교연산자>
  ex) priority_queue< int , vector<int> , greater<int> > pq  >>> 작은순서( top( ) 기준 오름차순 )
       priority_queue< int , vector<int> , less<int> > pq  >>> 큰 순서( top( ) 기준 내림차순 )
  이 부분을 알고가자.