BOJ 1927 최소 힙(C++, min/max heap)

최소 힙을 써볼 일이 있어서 개념도 집고 넘어갈 겸 문제를 풀어 보았다.

#define _CRT_SECURE_NO_WARNINGS
#include    <iostream>
#include	<math.h>
using namespace std;

#define MAX_SIZE 100001 


class MinHeap {
private:
	int heap[MAX_SIZE];     // heap[0] : top(smallest) item
	int heap_size = 0;
	int root = 1; // 0번은 안쓰고 1번부터 쓸 예정

	// 부모 노드 인덱스 계산
	int parent(int i) 
	{
		return i / 2;
	}

	// 왼쪽 자식 노드 인덱스 계산
	int left(int i) 
	{
		return 2 * i;
	}

	// 오른쪽 자식 노드 인덱스 계산
	int right(int i) 
	{
		return 2 * i + 1;
	}

	// 힙 속성 유지 (Min Heapify)
	void minHeapify(int i) {
		int l = left(i);
		int r = right(i);
		int smallest = i;

		if (l <= heap_size && heap[l] < heap[smallest]) {
			smallest = l;
		}

		if (r <= heap_size && heap[r] < heap[smallest]) {
			smallest = r;
		}

		if (smallest != i) {
			int t = heap[i];
			heap[i] = heap[smallest];
			heap[smallest] = t;
			minHeapify(smallest); // 재귀적으로 힙 속성 유지
		}
	}
public:
	void init()
	{
		heap[0] = 2>>31-1;
	}
	// 삽입 연산
	void push(int val) {
		heap[++heap_size] = val; // 한칸 늘려서 넣어줌 
		int i = heap_size; // 새 값 시작위치 
		// 힙 속성 유지
		while (i != root && heap[parent(i)] > heap[i]) // 루트노드위치가 아니고, 현재위치보다 부모위치가 크면 바껴야 함  
		{
			int t = heap[i];
			heap[i] = heap[parent(i)];
			heap[parent(i)] = t;
			i = parent(i); // 바뀌면 현재위치를 바뀐 부모위치로 해서 다시 확인
		}
	}

	// 최소값 반환 후 루트 노드 삭제
	int pop() 
	{
		if (heap_size == 0) {
			return 0; // 배열이 비어있는 경우 0 출력
		}

		int top = heap[root];
		heap[root] = heap[heap_size]; // 루트 위치에 마지막 노드 값 주고, 
		heap[heap_size--] = heap[0]; // 혹시 모르니 기존 마지막 위치에 쓰레기값(heap0번에 쓰레기값넣어둠) 줌
		minHeapify(root); //루트 노드 새로 갱신되었으니 히피파이 - 힙 규칙 다시
		//printHeap();
		return top;
	}

	// 최소값 반환 (삭제하지 않음)
	int top() {
		if (heap_size == 0) {
			return 0; // 배열이 비어있는 경우 0 출력
		}
		return heap[root];
	}

	// 힙이 비어있는지 확인
	bool isEmpty() {
		return heap_size == 0;
	}

	// 힙 내용 출력 (디버깅용)
	void printHeap() {
		printf("HEAP : ");
		for (int i = 1; i <= heap_size; ++i) {
			printf("{%d} ", heap[i]);
		}
		printf("\n");
	}

	// 초기화
	void clear()
	{
		heap_size = 0;
	}
};


int main()
{
	int N;
	scanf("%d", &N);
	MinHeap h;
	h.init();
	int v;
	for (int i = 0; i < N; ++i)
	{
		scanf("%d", &v);
		if (v == 0)
		{
			printf("%d\n", h.pop());

			//h.printHeap();
		}
		else 
		{
			h.push(v);

			//h.printHeap();
		}
	}

	return 0;
}

최소 힙은 간단히 말하자면 이진트리인데, 부모와 자식간에 관계가 최소 힙이면 부모가 자식보다 무조건 작은 값을 가지고, 최대 힙이면 반대이다.
보통 루트노드를 0으로 설정하냐(배열의 시작이 보통 0이므로) 1로 설정하냐(인덱스 편하게 하려고) 에 따라 자식노드인덱스 위치나 부모노드 인덱스 위치 계산이 약간씩 달라지지만 실제로 몇개 작성해보면 계산법이 나온다.
루트노드가 1이면 2, 3이 자식이므로 root*2 , root*2+1 이자식노드 왼쪽 오른쪽이 된다. 이런 경우 부모노드는 그냥 나누기 2해주면 자동으로 부모노드가 된다.
우선순위큐로 보통 사용하는것으로 알고있고. 가장 작은 값을 꺼낼 때는 루트를 보면 된다. 그리고 어차피 루트값만 꺼낼 수 있으므로 해야할것은
새로운 값이 입력 될때, 루트값이 꺼내어질떄 두 경우에 최소 힙 구조를 만들어주면 된다.
새 값이 입력되는 경우에는 가장 뒤에 넣어주고(리프노드) 부모와 비교하면서 부모보다 작으면 부모 값과 자리를 바꿔서 올려보내고 아니면 그 자리에 멈추면 된다. 부모가 자식보다만 작은 수면 최소 힙이 유지가 되니 크게 어렵지 않다.
루트값이 꺼내어질때는 맨 아래 큰 값을 루트로 주고, 힙을 유지하기 위해 자식들을 확인하면서 다시 구조를 맞춰준다.
흔히 말하는 배열에서 하나씩 보고 최소값을 찾는것에 비해 (O(n)), 바로 찾을 수 있으므로 바로 찾고 다시 힙 구조 맞춰주는것은 log2n(완전이진트리이므로 자식이 2개씩 달릴때마다 뎁스가 늘어나니까 트리의 뎁스만큼만 체크) 라서 훨씬 빠르게 된다.