[백준 11279] 최대 힙

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

11279번: 최대 힙

 

 

문제 요구 사항

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

 

1번 풀이

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

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

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

 

2번 풀이

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

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

 

 

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

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

 

 

코드

 

#include <stdio.h>
#define MAX_N 100001

int heap[MAX_N];
int size = 0;

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void insert(int data) {
	int idx = ++size;

	while ((idx != 1) && (data>heap[idx / 2])) {
		heap[idx] = heap[idx / 2];
		idx /= 2;
	}
	heap[idx] = data;
}

int deleteheap() {
	if (size == 0)
		return 0;
	int value = heap[1];
	//1에  힙에 제일 마지막에 있는 데이터 삽입 
	heap[1] = heap[size--];
	int parent = 1;
	int child;

	while (1) {
		child = parent * 2;
		//왼쪽 오른쪽 선택하는거 
		if (child + 1 <= size && heap[child] <heap[child + 1])
			child++;

		if (child > size || heap[child] < heap[parent])
			break;

		swap(&heap[parent], &heap[child]);
		parent = child;
	}

	return value;

}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int x;
		scanf("%d", &x);
		if (x == 0)
		{
			printf("%d\n", deleteheap());
		}
		else
		{
			insert(x);
		}
	}


}