[백준] 1927번: 최소 힙 (C언어)

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

1927번: 최소 힙

난이도: solved.ac 실버 2

 

 

그냥 우선순위 큐 구현 문제다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define HEAP_LEN 100001
#define TRUE 1
#define FALSE 0

typedef int PriorityComp(int d1, int d2);

typedef struct _heap {
	PriorityComp* comp;
	int numOfData;
	int arr[HEAP_LEN];
} Heap;

void HeapInit(Heap* ph, PriorityComp pc);
int HIsEmpty(Heap*);
int GetParentIDX(int);
int GetLChildIDX(int);
int GetRChildIDX(int);
int DataPriorityComp(int, int);
int GetHighPriChildIDX(Heap*, int);
void HInsert(Heap*, int);
int HDelete(Heap*);

int main() {
	int N, num, i;
	Heap heap;
	HeapInit(&heap, DataPriorityComp);

	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &num);
		if (num == 0)
			printf("%d\n", HDelete(&heap));
		else
			HInsert(&heap, num);
	}
	return 0;
}

int DataPriorityComp(int d1, int d2) {
	return d1 - d2;
}

void HeapInit(Heap* ph, PriorityComp pc) {
	ph->numOfData = 0;
	ph->comp = pc;
}

int HIsEmpty(Heap* ph) {
	if (ph->numOfData == 0)
		return TRUE;
	else return FALSE;
}

int GetParentIDX(int idx) {
	return idx / 2;
}

int GetLChildIDX(int idx) {
	return idx * 2;
}

int GetRChildIDX(int idx) {
	return idx * 2 + 1;
}

int GetHighPriChildIDX(Heap* ph, int idx) {
	if (GetLChildIDX(idx) > ph->numOfData)
		return 0;
	else if (GetLChildIDX(idx) == ph->numOfData)
		return GetLChildIDX(idx);
	else {
		if (ph->comp(ph->arr[GetLChildIDX(idx)], ph->arr[GetRChildIDX(idx)]) < 0)
			return GetLChildIDX(idx);
		else return GetRChildIDX(idx);
	}
}

void HInsert(Heap* ph, int data) {
	int idx = ph->numOfData + 1;

	while (idx != 1) {
		if (ph->comp(data, ph->arr[GetParentIDX(idx)]) < 0) {
			ph->arr[idx] = ph->arr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else break;
	}
	ph->arr[idx] = data;
	(ph->numOfData)++;
}

int HDelete(Heap* ph) {
	if (HIsEmpty(ph))
		return 0;

	int retData = ph->arr[1];
	int lastElem = ph->arr[ph->numOfData];

	int parentIdx = 1;
	int childIdx;

	while (childIdx = GetHighPriChildIDX(ph, parentIdx)) {
		if (ph->comp(lastElem, ph->arr[childIdx]) <= 0)
			break;
		ph->arr[parentIdx] = ph->arr[childIdx];
		parentIdx = childIdx;
	}
	ph->arr[parentIdx] = lastElem;
	(ph->numOfData)--;
	return retData;
}