문제

풀이

• 힙

  • 이진 트리 기반 자료구조
  • 중복 허용

• 기능

1. 삽입 push(x)
2. 최소값 출력 peek()
3. 최소값 제거 pop()

• 배열로 구현

1. 배열 인덱스 : 노드의 key(우선순위)를 의미한다. 부모자식 관계를 편하게 계산하기 위해 인덱스 0은 패스하고 1부터 시작한다.
2. 부모 key : 자식 key / 2
   자식 key : 부모 key 2 혹은 부모 key 2 + 1
3. 입력 : N(연산 개수), x(자연수 또는 0)
   -> x가 0이 아닌 자연수 : x 값을 삽입
   -> x가 0 : 루트 노드 값을 출력하고 배열에서 그 값을 제거한다.

• 삽입
  마지막 노드 다음에 삽입, 부모가 더 작을 때까지 부모와 비교하면서 올라가기
  (마지막 노드의 key는 총 노드 개수와 같다)
  1) 배열[마지막 노드+1] 에 삽입
  2) 부모인 배열[(마지막 노드+1)/2] 과 값 비교해서 부모보다 작으면 swap
  3) 부모가 더 작거나, 부모가 없을 때까지 반복

#include <iostream>
#include <algorithm>

using namespace  std;


int arr[100001];
// last : 마지막 노드의 인덱스
int last = 0;

void push(int X) {
	if (100000 <= last) return;
	// idxCur : 현재 노드의 인덱스, 먼저 맨 끝에 삽입하므로 last+1 이다
	int idxCur = ++last;
	arr[idxCur] = X;
	// 부모가 있을 때, 부모보다 작은지 비교
	while (arr[idxCur] < arr[idxCur / 2] && 0 != arr[idxCur / 2]) {
		// 부모보다 작다면 값 맞바꾸기
		swap(arr[idxCur], arr[idxCur / 2]);
		// 인덱스 업데이트
		idxCur /= 2;
	}
}

int pop() {
	if (0 == last)
		return 0;

	// root : 루트 노드 값 복사, cur : 현재 노드의 인덱스
	int root = arr[1], cur = 1;
	// 루트 노드 비우고, 그 위치에 마지막 노드 대입
	arr[1] = 0;
	swap(arr[1], arr[last--]);
	// 자식이 더 작은지 비교
	while (arr[cur] > arr[2 * cur] || arr[cur] > arr[2 * cur + 1])
	{
		// 왼쪽 자식
		if (0 != arr[2 * cur]) {
			
		}
		// 오른쪽 자식
		// 자식이 더 작다면 맞바꾸기
		// 인덱스 업데이트
	}

	// pop한 노드 값 반환
	return root;
}

int main() {
	int N, x;
	cin >> N;
	while (N--) {
		cin >> x;
		if (0 == x) cout << pop() << "\n";
		push(x);
	}

	return 0;
}

참고
https://yabmoons.tistory.com/374