[c++] 최대힙, 최소힙 - priority_queue : 우선순위 큐

최대힙

최대힙은 완전이진트리로 구현된 자료구조이며

구성은 부모의 노드값이 왼쪽과 오른쪽 자식의 노드 값보다 크게 트리를 구성하는 것을 말한다.

이렇게 하는 트리의 루트노드는 입력된 값들 중 가장 큰 값이 저장되어 있다.

만약 1,2,3,4,5,6,7이 값으로 입력되면 트리는 아래와 같이 구성된다.

최대힙 예제코드

#include <iostream>
#include <vector>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
	//freopen("input.txt", "rt", stdin);
	int a;
	priority_queue<int> pQ;
	while(true){
		scanf("%d", &a);
		if(a==-1) break;
		if(a==0){
			if(pQ.empty()) printf("-1\n");
			else {
				printf("%d\n", pQ.top());
				pQ.pop();
			}
		}
		else pQ.push(a);
	}
	
	return 0;
}

1) 자연수가 입력되면 최대힙에 입력한다.

2) 숫자 0 이 입력되면 최대힙에서 최댓값을 꺼내어 출력한다. (출력할 자료가 없으면 -1를 출력한다.)

3) -1이 입력되면 프로그램 종료한다.

위와같은 조건을 만족하는 프로그램을 작성하는 코드이다.

 

 

최소힙

최소힙은 완전이진트리로 구현된 자료구조이며

구성은 부모의 노드값이 왼쪽과 오른쪽 자식의 노드 값보다 작게 트리를 구성하는 것을 말한다.

이렇게 하는 트리의 루트노드는 입력된 값들 중 가장 작은 값이 저장되어 있다.

만약 1,2,3,4,5,6,7이 값으로 입력되면 트리는 아래와 같이 구성된다.

최소힙 예제코드

#include <iostream>
#include <vector>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
	freopen("input.txt", "rt", stdin);
	int a, res;
	priority_queue<int> pQ;
	while(true){
		scanf("%d", &a);
		if(a==-1) break;
		if(a==0){
			if(pQ.empty()) printf("-1\n");
			else {
				printf("%d\n", -pQ.top());
				pQ.pop();
			}
		}
		else pQ.push(-a);
	}
	
	return 0;
}

1) 자연수가 입력되면 최소힙에 입력한다.

2) 숫자 0 이 입력되면 최소힙에서 최솟값을 꺼내어 출력한다. (출력할 자료가 없으면 -1를 출력한다.)

3) -1이 입력되면 프로그램 종료한다.

위와같은 조건을 만족하는 프로그램을 작성하는 코드이다.