[백준 11279번] 최대 힙

2020. 5. 28. 17:17Algorithm/practice

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

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이�

www.acmicpc.net

heap 자료구조를 이해하고 maxheap을 위한 insertion과 deletion을 구현하였다.

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define MAX_LEN 100001
int heap[MAX_LEN];
int answer[MAX_LEN];
int hidx = 0;
int aidx = 0;


void insertNode(int a) {
	heap[++hidx] = a;
	int child = hidx;
	int parent = child / 2;
	while (child > 1 && (heap[parent] < heap[child])) {
		swap(heap[parent], heap[child]);
		child = parent;
		parent = child / 2;
	}
}
void deleteNode(int a) {
	if (hidx < 1) {
		answer[aidx++] = 0;
		return;
	}
	else {
		answer[aidx++] = heap[1];
		swap(heap[1], heap[hidx--]);
		int parent = 1;
		int child = parent * 2;
		//child 2명 중에 큰 값을 child로 정하기  
		if (child + 1 <= hidx) {
			child = (heap[child] > heap[child + 1]) ? child : child + 1;
		}
		//1. child와 parent 비교했을 때 child가 크면 바꾸기
		//2. 그 다음 level이 있을 경우, 그 다음 level에 있는 child 중 큰 값을 child로 정한다.
		while (child <= hidx && (heap[parent] < heap[child])) {
			swap(heap[parent], heap[child]);
			parent = child;
			child = child * 2;
			if (child + 1 <= hidx) {
				child = (heap[child] > heap[child + 1]) ? child : child + 1;
			}
		}
	}
}
int main() {
	int num;
	int a;
	scanf("%d", &num);
	heap[0] = -1;
	for (int i = 0; i < num; i++) {
		scanf("%d",&a);
		if (a == 0) {
			deleteNode(a);
		}
		else {
			insertNode(a);
		}
	}
	for (int i = 0; i < aidx; i++) {
		printf("%d\n", answer[i]);
	}
	return 0;
}

'Algorithm > practice' 카테고리의 다른 글

[백준 2523번] 별찍기-13  (0) 2020.07.08
[백준 1110번] 더하기 사이클  (0) 2020.07.08
[백준 10996번] 별찍기-21  (0) 2020.07.08
[백준 9093] 단어 뒤집기  (0) 2020.07.02
[백준 1697번] 숨바꼭질  (0) 2020.05.22