[BAEKJOON] 1927번 : 최소 힙

문 제

 

소 스  코 드

#include <iostream>

typedef long long element;
constexpr int MIN{ 0 };
constexpr int ROOT{ 1 };
constexpr element MAXINT{ 0x8000'0000 };

class MinHeap {
public:
	MinHeap() = delete;
	MinHeap(const int& size) : m_size{ size }, m_ptr{ 1 }, m_heap{ new element[size] }{
		std::fill_n(m_heap, m_size, MAXINT);
		m_heap[0] = MIN;
	}
	~MinHeap() {
		delete[] m_heap;
	}


	void Insert(const element& val) {
		int now_ptr{ m_ptr };
		m_heap[now_ptr] = val;

		int parent{ now_ptr / 2 };
		// parent compare
		while ((1 != now_ptr) && (m_heap[now_ptr] < m_heap[parent])) {
			Swap(now_ptr, parent);

			now_ptr = parent;
			parent = now_ptr / 2;
		}

		++m_ptr;
	}

	element Pop() {
		if (m_ptr < 2) return 0;
		element now = m_heap[ROOT];
		--m_ptr;

		m_heap[ROOT] = m_heap[m_ptr];
		m_heap[m_ptr] = MAXINT;

		int now_ptr{ ROOT };
		int child_ptr;

		if (m_heap[now_ptr * 2] <= m_heap[(now_ptr * 2) + 1])	child_ptr = now_ptr * 2;
		else													child_ptr = (now_ptr * 2) + 1;

		while (m_heap[now_ptr] > m_heap[child_ptr]) {
			Swap(now_ptr, child_ptr);

			now_ptr = child_ptr;

			if ((now_ptr * 2) > m_ptr) break;

			if (m_heap[now_ptr * 2] <= m_heap[(now_ptr * 2) + 1])	child_ptr = now_ptr * 2;
			else													child_ptr = (now_ptr * 2) + 1;

		}
		return now;
	}

	void Swap(const int& left, const int& right) {
		element temp = m_heap[left];
		m_heap[left] = m_heap[right];
		m_heap[right] = temp;
	}

	void Display() {
		for (int i = 1; i < m_ptr; ++i) std::cout << m_heap[i] << "  ";
		std::cout << '\n';
	}

private:
	element *m_heap;
	int m_size;
	int m_ptr;

};


int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N;
	std::cin >> N;

	MinHeap mh{ N + 1 };

	int num;
	for (int i = 0; i < N; ++i) {
		std::cin >> num;

		if (0 == num) {
			std::cout << mh.Pop() << '\n';
		}
		else {
			mh.Insert(num);
		}
	}
	return 0;
}

 

풀 이

 

• 힙이란?

최소 힙은 꼭대기가 가장 작은 수가 되는 이진 트리 구조이다.

힙은 고정된 배열을 통하여 만들 수 있고, 포인터를 이용하여 구현 할 수 있다.

배열로 구현 할 경우에는,

 

왼쪽 자식 = ( 부모 * 2 ) 
오른쪽 자식 = ( 부모 * 2 ) + 1

부모 자식 = 자식 / 2

 

을 사용하기 위해서는 배열의 모든 값들을 int의 최댓값으로 초기화 해주고,

배열의 0번째 인덱스의 값을 0으로 하여,
원하는 조건에 맞게 구현하는 것이 가능하다.

 

부모의 왼쪽 자식이 없을 경우 자식이 없다는 규칙도 존재하다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/1927

1927번: 최소 힙