BOJ - 최대 힙(11279)

배열을 사용해서 간단하게 구현한 최대 힙(MaxHeap)입니다. 코드의 길이를 줄이기 보다는 가독성을 높이는 방향으로 작성했습니다.

최대 힙

// 최대힙 초기화
int maxHeap[200005];
int lastIdx = 0;

// 자식 노드 Index 
int getLeftChild(int idx) {
	return idx * 2;
}

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

// 부모 노드 Index 
int getParent(int idx) {
	return idx / 2;
}

// 교환하는 함수
void swap(int idx1, int idx2, int* arr) {
	int tmp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = tmp;
}

// dequeue 함수
int dequeue() {
	
	if (lastIdx == 0) return 0;

	int head = maxHeap[1];
	maxHeap[1] = maxHeap[lastIdx];
	maxHeap[lastIdx] = 0;
	lastIdx--;

	int curIdx = 1;
	while (true) {
		int rIdx = getRightChild(curIdx);
		int lIdx = getLeftChild(curIdx);

		int curVal = maxHeap[curIdx];
		int rVal = maxHeap[rIdx];
		int lVal = maxHeap[lIdx];
		
		int nextIdx = rVal > lVal ? rIdx : lIdx;
		int nextVal = maxHeap[nextIdx];
		if (curVal < nextVal) {
			swap(curIdx, nextIdx, maxHeap);
			curIdx = nextIdx;
		} else {
			break;
		}
	}

	return head;
}

// enqueue 함수
void enqueue(int val) {
	lastIdx++;
	maxHeap[lastIdx] = val;

	int curIdx = lastIdx;
	while (true) {
		if (curIdx == 1) break;

		int pIdx = getParent(curIdx);
		
		int curVal = maxHeap[curIdx];
		int pVal = maxHeap[pIdx];

		int nextIdx = pIdx;
		int nextVal = maxHeap[nextIdx];
		if (curVal > nextVal) {
			swap(curIdx, nextIdx, maxHeap);
			curIdx = nextIdx;
		} else {
			break;
		}
	}
}

메인 함수

#include <stdio.h>

int main() {
	
	int N;
	scanf("%d", &N);

	while (N--) {
		int x;
		scanf("%d", &x);

		if (x > 0) {
			enqueue(x);
		} else if (x == 0) {
			int val = dequeue();
			printf("%d\n", val);
		}
	}

	return 0;
}