문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

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

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

접근

새로 접하는 자료구조라 최소 힙 관련 자료를 찾아보고 코딩하였다. 반정렬 상태의 이진트리를 힙이라 부르며, 삽입/삭제 기능을 가진다. 우선순위 큐를 구현할때 많이 사용하는 자료구조이다.

최소 힙이므로, 자식 노드로 진행될수록 값이 커지며 루트 노드에 최소값이 자리한다. 자료 삽입시, 트리의 마지막 인덱스에 삽입되어 부모노드와 반복적으로 값을 비교하며 올바른 위치에 자리잡는다. 자료 삭제시, 루트 노트를 제거하고 마지막 인덱스의 값을 루트 노드에 자리한 뒤 자식노드와 반복적으로 값을 비교하며 올바른 위치에 자리잡는다.

처음 본 자료구조라 혼자 용을 써도 헤멨지만, 자료구조 자체를 공부하고 구현하니 크게 어렵지 않았다. 첫 구현이라 내장 함수를 사용하지 않고 직접 작성해보았다.

코드

import java.util.Scanner;

public class Main {
	public static class Heap {
		int [] h;
		int index;
		
		public Heap(int n) {
			h = new int[n+1];
			index = 1;
		}
		
		public void insert(int data) {
			h[index] = data;
			int p = index;
			while(p!=1 && h[p] < h[p/2]) {
				int tmp = h[p];
				h[p] = h[p/2];
				h[p/2] = tmp;
				p /= 2;
			}
			index++;
		}
		
		public int delete() {
			int tmp = h[1];
			h[1] = h[--index];
			
			int now = 1;
			while(now*2<index) {
				int min = h[now*2];
				int minpos = now*2;
				if(now*2+1 < index && min > h[now*2+1]) {
					min = h[now*2+1];
					minpos = now*2+1;
				}
				if(h[now] < min)
					break;
				else {
					int swap = h[now];
					h[now] = h[minpos];
					h[minpos] = swap;
					now=minpos;
				}
			}
			return tmp;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Heap heap = new Heap(n);
		
		int [] command = new int[n];
		for(int i = 0; i < n; i++) {
			command[i] = sc.nextInt();
		}
		for(int i = 0; i < n; i++) {
			if(command[i] == 0) {
				if(heap.index == 1)
					System.out.println("0");
				else 
					System.out.println(heap.delete());
			}
			else
				heap.insert(command[i]);
		}
		
		
	}

}