[BOJ_1927 | Heap] 최소 힙

풀이 

최소 힙(MIn Heap)을 직접 구현하는 문제였다.

Heap은 연결 리스트로 구현하는 것 보다는 배열(Array)을 이용해서 구하는 것이 

정신건강에도 좋고 구현하기 편리하다. 

배열로 힙을 구현하면, 물론 데이터의 수를 알 수 없는 경우에는 저장 공간의 낭비가 생길 수 있겠지만

그 경우에도 추가적인 메소드 구현을 통해 공간을 줄여주거나 공간을 늘려주면 되므로 큰 무리는 없다.

가장 좋은 점은 Left Child, Right Child, Parent의 데이터를 index만으로 접근할 수 있다는 점이다.

index 0부터 시작하는 경우에는

Left Child = i*2+1

Right Child = i*2+2

Parent = (i-1)/2

로 접근할 수 있다.

소스 코드

import java.util.*;
public class BOJ_1927 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        Heap heap = new Heap();
        for(int i=0;i<n;i++){
            int num = input.nextInt();
            if(num == 0) heap.poll();
            else heap.add(num);
        }
    }
}
class Heap{
    private static final int DEFAULT_CAPACITY = 100000;
    private int[] arr;
    int size;
    Heap(){
        this.arr = new int[DEFAULT_CAPACITY];
        this.size = 0;
    }
    private int getLeftChildIndex(int i){return i*2+1;}
    private int getRightChildIndex(int i){return i*2+2;}
    private int getParentIndex(int i){return (i-1)/2;}
 
    private boolean hasLeftChild(int i){return getLeftChildIndex(i)<size;}
    private boolean hasRightChild(int i){return getRightChildIndex(i)<size;}
    private boolean hasParent(int i){return getParentIndex(i)>=0;}
 
    private void swap(int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    private void heapifyUp(int i){
        while(hasParent(i) && (arr[i]) < arr[getParentIndex(i)]){
            swap(i, getParentIndex(i));
            i = getParentIndex(i);
        }
    }
    private void heapifyDown(int i){
        while (hasLeftChild(i)) {
            int k = getLeftChildIndex(i);
            if(hasRightChild(i) && arr[getRightChildIndex(i)] < arr[getLeftChildIndex(i)])
                k = getRightChildIndex(i);
            if(arr[i]<arr[k]) break;
            else swap(i, k);
            i = k;
        }
    }
 
    public void add(int val){
        arr[size++] = val;
        heapifyUp(size-1);
    }
    public void poll(){
        if(size == 0) {System.out.println(0);return;}
        int val = arr[0];
        arr[0] = arr[--size];
        arr[size] = -999999;
        heapifyDown(0);
        System.out.println(val);
    }
}