[백준 / C언어] 11279번: 최대 힙(배열로 구현)

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

11279번: 최대 힙

 

난이도: solved.ac 실버 2

 

 

자료구조 힙(Heap)을 구현하는 문제다

 

일반 이진트리(Binary Tree)는 input이 100,000개일 때 높이(depth)가 2^100000 - 1가 될 수 있지만

(한쪽으로만 연결된 경우에)

 

힙은 완전 이진트리(Complete Binary Tree)라서 input이 100,000개여도 높이는 log(2)100,000 밖에 되지 않는다

 

따라서 배열로 구현해도 무방할 것 같다는 생각이 들어 배열을 이용해 만들어보았다

 

 

#include<stdio.h>
#define MAX 100001
 
typedef struct _Heap {
	int numOfData;
	int arr[MAX];
} Heap;
 
void initHeap(Heap* heap);
void Insert(Heap* heap, int data);
int Delete(Heap* heap);
 
int main() {
	int n, x, i;
	Heap heap;
	initHeap(&heap);
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &x);
		if (x == 0) {
			if (!heap.numOfData)
				printf("0\n");
			else
				printf("%d\n", Delete(&heap));
		}
		else {
			Insert(&heap, x);
		}
	}
 
	return 0;
}
 
void initHeap(Heap* heap) {
	heap->numOfData = 0;
}
 
void Insert(Heap* heap, int data) {
	int idx = heap->numOfData + 1;
	while (idx != 1) {
		if (data > heap->arr[idx / 2]) {
			heap->arr[idx] = heap->arr[idx / 2];
			idx /= 2;
		}
		else
			break;
	}
	heap->arr[idx] = data;
	heap->numOfData++;
}
 
int Delete(Heap* heap) {
	int root = heap->arr[1];
	int last = heap->arr[heap->numOfData];
	heap->numOfData--;
 
	int pIdx = 1, Lchild = pIdx * 2, Rchild = pIdx * 2 + 1;
	int cIdx;
	while (Lchild <= heap->numOfData) {
		if (Lchild == heap->numOfData) {
			if (last < heap->arr[Lchild]) {
				cIdx = Lchild;
				heap->arr[pIdx] = heap->arr[cIdx];
				pIdx = cIdx;
			}
			break;
		}
		else {
			cIdx = heap->arr[Lchild] > heap->arr[Rchild] ? Lchild : Rchild;
			if (last > heap->arr[cIdx])
				break;
			else
				heap->arr[pIdx] = heap->arr[cIdx];
		}
		pIdx = cIdx;
		Lchild = pIdx * 2;
		Rchild = pIdx * 2 + 1;
	}
	heap->arr[pIdx] = last;
	return root;
}