Baekjoon_1927_최소힙

문제 설명

1927번: 최소 힙

• N개의 수가 주어짐
• 정수 x에 따라
  • 0이 아니면 : 정수 x를 배열에 저장
  • 0이면 : 배열에 저장된 값 중 제일 작은 값 출력. 배열에 값이 없다면 0 출력.

 

 

문제 풀이

트리

원소들을 계층적으로 저장하는 비선형 자료구조

 

이진트리

하나의 노드가 최대 2개의 자식노드를 가지는 트리구조

[DS] 이진 트리 - binary tree (개념 및 이진 트리의 종류)

그 중 부모 자식간의 대소관계는 정해져 있으면서, 형제간의 대소관계가 정해지지 않은 트리구조가 힙이다.

 

자식노드 = 부모노드 * 2, 부모노드 * 2 +1

 

부모노드 = 자식노드 / 2

 

최소 힙

push : 배열의 제일 마지막에 값을 넣고, 그 부모와 비교해 부모보다 작은 값이면 자리를 바꾸면서 정렬.

pop : 배열의 가장 앞자리(1)을 빼고, 가장 마지막 위치의 값을 맨 앞자리에 넣는다. 그리고 그 자식노드들과 비교해 더 큰 값이면 자리를 바꾸면서 정렬한다. 

 

문제 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class _1927_최소힙 {
	static int heap[], size = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		heap = new int[N];
		for (int i = 0; i < N; ++i) {	//num 값에 따라 배열에서 값을 꺼낼지 넣을지 결정
			int num = Integer.parseInt(in.readLine());
			if(num == 0) {
				System.out.println(pop());
			}else {
				push(num);
			}
		}
	}
	
	static void push(int num) {
		int idx = ++size;
		while((idx != 1) && (num<heap[idx/2])) {	//자식보다 작은 값이면 앞쪽으로 자리 바꾸기
			heap[idx/2] ^= heap[idx];
			heap[idx] ^= heap[idx/2];
			heap[idx/2] ^= heap[idx];
			idx /= 2;
		}
		heap[idx] = num;
	}
	
	static int pop() {
		if(size == 0) {
			return 0;
		}
		int result = heap[1];	//제일 앞의 값 꺼내기(제일 작은 것)
		heap[1] = heap[size--];
		int parent = 1;
		int child;
		while(true) {
			child = parent*2;
			if(child+1 <= size && heap[child] > heap[child+1]) {	//더 작은 자식 노드 찾기
				child++;
			}
			if(child>size || heap[child] > heap[parent]) {	//범위 밖이거나 자식보다 작은 값이면 나가기
				break;
			}
            //자리 바꾸기
			heap[child] ^= heap[parent];
			heap[parent] ^= heap[child];
			heap[child] ^= heap[parent];
			parent = child;
		}
		return result;
	}
}