[자료구조] PriorityQueue(HEAP).c

우선순위 큐

 

표현은 이진트리(BinaryTree) 로 하는데 성질은 Queue임

 

/* 백준 solved
* 이진탐색트리 <- 힙으로 표현 <- 배열로 구현
* 힙 == "완전"이진트리
* 우선순위 함수 필요 (사용자정의)
*/

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

#define HEAP_LEN 100

typedef int HData; // 자료형만 바꿔주기

typedef int (*PriorityComp)(HData d1, HData d2);

typedef struct _heap {
	HData heapArr[HEAP_LEN];
	int numOfData;
	PriorityComp comp;
}Heap;

void HeapInit(Heap* ph, PriorityComp pc) { 
	ph->numOfData = 0; 
	ph->comp = pc; // 우선순위함수 배정
}

int HIsEmpty(Heap* ph) { return ph->numOfData == 0 ? 1 : 0; }

int GetParentIndex(int idx) { return idx / 2; }
int GetLChildIndex(int idx) { return idx * 2; }
int GetRChildIndex(int idx) { return idx * 2 + 1; }

int GetHiPriChild(Heap* ph,int idx) {
	if (GetLChildIndex(idx) == ph->numOfData) { return GetLChildIndex(idx); }
	
	if (GetLChildIndex(idx) > ph->numOfData) { return 0; }
	
	if ((*(ph->comp))(ph->heapArr[GetLChildIndex(idx)], ph->heapArr[GetRChildIndex(idx)]) < 0) { return GetLChildIndex(idx);}
	else { return GetRChildIndex(idx); }
}

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

	// 밑에서 위로 자리찾기
	// data가 부모보다 우선이면
	while (idx != 1) {
		if ((*(ph->comp))(data,ph->heapArr[GetParentIndex(idx)]) < 0) {
			ph->heapArr[idx] = ph->heapArr[GetParentIndex(idx)];
			idx = GetParentIndex(idx);
		}
		else {
			break;
		}
	}
	ph->heapArr[idx] = data;
	ph->numOfData+=1;
}

HData HDelete(Heap* ph) {
	HData retData = ph->heapArr[1];
	
	HData lastData = ph->heapArr[ph->numOfData];
	int parentIdx = 1;
	int childIdx;

	// 위에서 아래로
	// childIdx가 0이면 맨 밑까지 내려갔다는 것
	while(childIdx = GetHiPriChild(ph,parentIdx)){
		// 자식이 더 우선이면
		if ((*(ph->comp))(ph->heapArr[childIdx],lastData) < 0) {
			ph->heapArr[parentIdx] = ph->heapArr[childIdx];
			parentIdx = childIdx;
		}
		else {
			break;
		}
	}

	/*
	while ((*(ph->comp))(ph->heapArr[GetHiPriChild(ph,idx)],lastData) > 0) {
		ph->heapArr[idx] = ph->heapArr[GetHiPriChild(ph, idx)];
		idx = GetHiPriChild(ph, idx);
	}
	
	ph->heapArr[idx] = lastData;
	*/

	ph->heapArr[parentIdx] = lastData;
	ph->numOfData--;
	return retData;
}

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

 

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

	HData data;

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