[BOJ 11279번] 최대 힙(JAVA)

www.acmicpc.net/problem/11279

11279번: 최대 힙

import java.io.*;
import java.util.*;

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   static StringBuilder sb=new StringBuilder();
   static int N;
   static int heap[]=new int[100001];
   static int top=0;
   
   public static void main(String args[]) throws Exception {
	   N=Integer.parseInt(br.readLine());
	   for(int i=0;i<N;i++) {
		   int num=Integer.parseInt(br.readLine());
		   if(num==0) {
			   if(top==0) sb.append(0+"\n");
			   else sb.append(pop()+"\n");
		   }
		   else {
			   push(num);
		   }
	   }
	   System.out.println(sb);
   }
   
   static void swap(int a, int b) {
	   int temp=heap[a];
	   heap[a]=heap[b];
	   heap[b]=temp;
   }
   
   static void push(int n) {
	   heap[++top]=n;
	   int i=top;
	   while(i>1&&heap[i/2]<heap[i]) {
		   swap(i, i/2);
		   i/=2;
	   }
   }
   
   static int pop() {
	   int result=heap[1];
//       sb.append(result+"\n");
	   heap[1]=heap[top];
	   heap[top--]=0;
	   for(int i=1;i*2<=top;) {
		   if(heap[i]>heap[i*2]&&heap[i]>heap[i*2+1]) break;
		   else if(heap[i*2]>heap[i*2+1]) {
			   swap(i, i*2);
			   i=i*2;
		   }
		   else {
			   swap(i, i*2+1);
			   i=i*2+1;
		   }
	   }
	   return result;
   }
   
}

 지난 번 포스팅 때 다뤘던 백준 최소 힙 문제는 priorityqueue 클래스를 이용해서 풀어봤는데요, 이번 최대 힙 문제는 직접 힙(heap)을 배열로 구현하여서 풀어보았습니다.

힙(heap)은 완전 이진 트리로 부모 노드와 자식 노드끼리 값을 비교하기 때문에 시간 복잡도가 높지 않다는 특징을 가지고 있습니다.

여기서 구하는 최대 힙은 부모 노드의 값이 자식 노드의 키 값보다 크거나 같다 라는 특징을 이용해서 풀어야 합니다.

이를 위해 swap 함수, push 함수, pop함수를 구현했고, 일차 배열을 이용해 힙을 구현했습니다. 

스택을 구현할 때 했던 것 처럼 top이란 변수를 만들어서 힙을 관리했습니다.

시간이 된다면 다음 포스팅 때 힙에 대해 자세히 다뤄보도록 하겠습니다.