개요

백준 11279(최대 힙)

• 입력
  첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

• 출력
  입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

접근 방식

1. 사실 STL안의 priority_queue사용하면 쉽게 구현이 가능하지만,
   한번 배열을 사용해 max heap 구조를 만들어봤다.

2. 기본적으로 maxheap은 index를 1부터 시작한다.

3. 원소가 push되면 배열의 맨 마지막에 넣은 후,
   재귀를 통해 해당 인덱스 > 인덱스/2 일때마다 바꿔준다.

4. 원소가 pop되면 루트 값과 제일 마지막 원소의 위치를 바꾼 뒤,
   루트값을 제거한 후, 루트index에 온 마지막 원소를 재귀를 통해
   제 위치로 찾아간다.

전체 코드

#include<iostream>

using namespace std;

//기본적으로 마지막 빈칸이랑 마지막 원소찾을때를 잘못 생각했는데,
//추가할때 인덱스를 그냥 마지막 인덱스 다음 인덱스에 넣으면 되는데, 
//빈칸 인덱스를 찾을 때 밑에 자식이 있으면 오른쪽 자식으로 넘어가고 해당 자식에서 또 왼쪽 자식 검색하고 이런식으로 
//오른쪽 자식노드가 없을때까지 반복하는식으로 구현해서 이상한 값을 자꾸 넘겨줬다. 

//maxHeap
class Priority_Queue {
private:
	int* pq;
	//큐안의 원소 갯수, 마지막 원소가 들어있는 인덱스로 사용
	int size;

public:
	Priority_Queue(int n) {
		pq = new int[n];
		size = 0;
		fill(&pq[0], &pq[n], -1);
	}

	void Push(int x);
	void Pop();
	void Heapify(int curIdx);
};

void Priority_Queue::Push(int x) {
	//비어있을 경우
	if (pq[1] == -1) {
		pq[1] = x;
		size = 1;
		return;
	}

	int cur_idx = ++size;
	//배열의 마지막 칸에 x를 넣어준다.
	pq[cur_idx] = x;

	//방금 들어온 원소 x를 맞는 위치에 넣어주기
	while (1) {
		//현재 idx가 루트 노드라면 return
		if (cur_idx / 2 == 0) return;

		//부모 노드가 자식 노드값보다 작다면 
		if (pq[cur_idx / 2] < pq[cur_idx]) {
			//바꿔주기
			swap(pq[cur_idx / 2], pq[cur_idx]);
			cur_idx /= 2;
		}
		else
			break;
	}
	return;
}

void Priority_Queue::Pop() {
	//비어있다면 0출력
	if (pq[1] == -1) {
		cout << 0 << '\n';
		return;
	}
	//루트 노드 출력
	cout << pq[1] << "\n";
	int lastIndex =size--;
	//마지막 원소와 루트 노드 바꾸기
	swap(pq[1], pq[lastIndex]);
	//루트 노드값 제거
	pq[lastIndex] = -1;

	
	if (lastIndex != 1)
		Heapify(1);
}

/// <summary>
/// pop 후에 루트노드에 박힌 원소값 제자리 넣어주는 재귀함수
/// </summary>
/// <param name="curIdx(제자리 찾아가야할 원소의 현재 index)"></param>
void Priority_Queue::Heapify(int curIdx) {
	//curIdx가 범위를 벗어나면 리턴
	if (curIdx * 2 > 100'002) return;
	//curIdx가 범위를 만족하지만 리프노드라면 리턴
	if (curIdx * 2 <= 100'002 && pq[curIdx * 2] == -1) return;
	//임시 인덱스 tmp_idx에 curIdx값 저장
	int tmp_idx = curIdx;
	//tmp_idx 두배 해줌
	tmp_idx *= 2;
	//왼쪽 자식 오른쪽 자식 비교해 더 큰값으로 tmp_idx옮김
	if (tmp_idx + 1 <= 100'002 && pq[tmp_idx] < pq[tmp_idx + 1])
		tmp_idx++;
	//자식중에 더 큰값보다 현재값이 더 크다면 리턴
	if (pq[curIdx] > pq[tmp_idx]) return;
	swap(pq[tmp_idx], pq[curIdx]);
	Heapify(tmp_idx);
}

void Input() {
	//연산이 10만이라했으므로 10만으로 초기화
	Priority_Queue* pq = new Priority_Queue(100'001);
	int N = 0, tmp = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		if (tmp == 0) {
			pq->Pop();
		}
		else
			pq->Push(tmp);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();

}

문풀후생

하지만 뭐에 홀렸는지 마지막 원소를 찾는 과정을
재귀를 통해 전체 트리에서 제일 오른쪽 리프노드를 찾게끔 설계해서 계속 오답이 나왔다.