자바의 PriorityQueue는 내부적으로 힙(Heap)을 통해 구현된다.
힙은 최소 힙, 최대 힙으로 구분된다.
최소 힙 구현
아래는 Java로 구현된 최소 힙이다.
package baekjoon.class_.class3.최소힙;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
MinHeap heap = new MinHeap(100000);
for(int i = 0; i<n; i++){
int k = Integer.parseInt(br.readLine());
if(k == 0) bw.write(heap.remove()+"\n");
else heap.add(k);
}
bw.flush();
}
static class MinHeap{
int[] arr;
int size = 0;
public MinHeap(int capacity){
arr = new int[capacity];
}
public void add(int num){
size++;
arr[size-1] = num;
compareWithParentAndSwap(size-1);
}
public int remove(){
if(size == 0) return 0;
int returnValue = arr[0];
arr[0] = arr[size-1];
arr[size-1] = 0;
size--;
compareWithChildAndSwap(0);
return returnValue;
}
private void compareWithParentAndSwap(int childIndex){
if(childIndex == 0) return;
int child = arr[childIndex];
int parentIndex = getParentIndex(childIndex);
int parent = arr[parentIndex];
if(child < parent){
arr[childIndex] = parent;
arr[parentIndex] = child;
compareWithParentAndSwap(parentIndex);
}
}
private void compareWithChildAndSwap(int parentIndex){
int parent = arr[parentIndex];
int leftChildIndex = getLeftChildIndex(parentIndex);
int rightChildIndex = getRightChildIndex(parentIndex);
if(rightChildIndex < size){ // 자식 노드가 모두 있는 경우
int leftChild = arr[leftChildIndex];
int rightChild = arr[rightChildIndex];
if(leftChild < rightChild){
if(leftChild < parent){
arr[parentIndex] = leftChild;
arr[leftChildIndex] = parent;
compareWithChildAndSwap(leftChildIndex);
}
}else{
if(rightChild < parent){
arr[parentIndex] = rightChild;
arr[rightChildIndex] = parent;
compareWithChildAndSwap(rightChildIndex);
}
}
}else if(leftChildIndex < size && size <= rightChildIndex){ // 왼쪽 자식만 있는 경우
int leftChild = arr[leftChildIndex];
if(leftChild < parent){
arr[parentIndex] = leftChild;
arr[leftChildIndex] = parent;
compareWithChildAndSwap(leftChildIndex);
}
}
}
private int getParentIndex(int childIndex){
return (childIndex-1) / 2;
}
private int getLeftChildIndex(int parentIndex){
return (parentIndex * 2) + 1;
}
private int getRightChildIndex(int parentIndex){
return (parentIndex * 2) + 2;
}
}
}
작동방식 설명
최소 힙은 자료구조 내 요소 중 가장 작은 값의 요소를 root에 위치시킨다.
조회
힙의 가장 첫 번째 요소(root) 리턴
insert
최소 힙에 요소를 삽입하여 정렬하는 과정은 다음과 같다.
delete
최소 힙의 첫 번째 요소를 삭제하는 과정은 다음과 같다.
시간 복잡도
조회
우선순위큐에서 가장 작거나 큰 요소를 조회하는 것은 root를 바로 가져오면 되므로, 시간복잡도가 1이다.
insert, delete
삽입 혹은 삭제는 이진트리로 구성된 자료구조의 각 계층을 순회하며 알맞은 자리를 찾아가기 때문에 logN의 시간복잡도를 가진다.
최대 힙 구현
최소 힙과 동일하게 구현하되, '최소'를 '최대'로, 혹은 '~보다 작다'를 '~보다 크다'로 바꿔주면 된다.