백준 알고리즘 1927번: 최소 힙

문제 정보

---

1927번: 최소 힙

 

핵심

---

최소 힙을 구현하거나, 이미 구현되어 있는 Collection 을 사용하면 된다

구현하는 경우에는 클래스를 만들어서, 풀어가면 되고 이미 있는 자료구조를 사용하려면 PriorityQueue (우선순위 큐)를 사용하면 된다

 

나는 그래도 힙에 대해서 다시금 정리할 겸 구현하여 풀이하는 식으로 풀어 나갔다

Heap 은 완전 이진 트리로 구현되는 자료구조이기 때문에, 노드의 개수를 알면 트리의 구조를 특정할 수 있다는 특징이 있다

그렇기 때문에, Heap 은 내부적으로 1차원 배열로 구현될 수 있으며 아래와 같은 인덱스로 구성된다

 

• 해당 노드의 부모 노드의 인덱스 -> (i - 1) / 2
• 해당 노드의 Left Child Node -> i * 2 + 1
• 해당 노드의 Right Child Node -> i * 2 + 2

 

또한 Heap 은 부모 노드의 값은 자식 노드의 값보다 무조건 크거나(Max Heap), 작아야(Min Heap) 한다

 

Min Heap으로 해당 문제가 풀이되므로, 최소 힙을 기준으로 설명하겠다

• Min Heap 의 경우, Root의 값이 가장 작다
• 따라서 가장 작은 값을 찾아내는 연산은 O(1) 이다

 

삽입 연산

맨 마지막에 노드 삽입 -> 자신의 부모 노드와 비교하여 내가 더 작으면 swap, 크면 그대로 (반복)

최악의 경우(가장 작은 수를 가지는 경우) 루트 노드까지 비교해야 하므로 O(log n) (높이)

 

삭제 연산

루트 노드 삭제 후 맨 마지막 노드를 루트로 옮김 -> 자신의 자식 노드 중 작은 숫자와 비교하여 자신이 크다면 swap, 작다면 그대로 (반복)

최악의 경우(가장 큰 수를 가지는 경우) 리프 노드까지 비교해야 하므로 O(log n) (높이)

 

풀이

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Heap heap = new Heap(N);

        for(int i=0; i<N; i++) {
            int input = Integer.parseInt(br.readLine());
            if(input == 0) {
                System.out.println(heap.pop());
            } else {
                heap.push(input);
            }
        }
    }
}

class Heap {
    private final int[] heap;
    private int size;

    public Heap(int maxSize) {
        this.heap = new int[maxSize];
        size = 0;
    }

    public void push(int number) {
        heap[size] = number;
        compareWithParent(size);
        size++;
    }

    public void compareWithParent(int index) {
        if(index == 0) {
            return;
        }
        int parent = (index - 1) / 2;
        if(heap[parent] > heap[index]) {
            swap(index, parent);
            compareWithParent(parent);
        }
    }

    public int pop(){
        if(size == 0) {
            return 0;
        }

        int min = heap[0];
        heap[0] = heap[size-1];
        size--;
        compareWithChild(0);

        return min;
    }

    public void compareWithChild(int index) {
        int leftChild = index * 2 + 1;
        int rightChild = index * 2 + 2;


        int minIndex = index;
        if(leftChild < size && heap[leftChild] < heap[minIndex]) {
            minIndex = leftChild;
        }
        if(rightChild < size && heap[rightChild] < heap[minIndex]) {
            minIndex = rightChild;
        }

        if(minIndex != index) {
            swap(index, minIndex);
            compareWithChild(minIndex);
        }
    }

    public void swap(int index1, int index2) {
        int tmp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = tmp;
    }
}

 

나는 재귀호출을 통하여 풀이하였지만, 여러 가지 이유로 반복문을 사용하는 것이 더 빠를 것이다

 

추가

---

 

11279번: 최대 힙

위 코드에서 부등호만 바꾸면, 최대 힙 문제도 가볍게 풀이할 수 있다!

 

Source Code on GitHub

---