[자료구조/문제] 중앙값(Median) 구하기, BOJ 2696, Heap

문제 : https://www.acmicpc.net/problem/2696

홀수번째 수를 읽을 때마다 지금까지 입력받은 수의 중앙값을 구하는 문제이다.

이 문제는 Heap을 이용하여 풀 수 있다.

Heap은 수를 담는 자료구조로, Java에서는 우선순위큐(PriorityQueue)로 구현할 수 있다.

Heap은 완전이진트리이며, 모든 정점은 자신의 자식보다 우선순위가 높다는 것이 중요한 성질 중 하나이다.

Top이 최대값인 우선순위큐를 최대힙(MaxHeap)

Top이 최소값인 우선순위큐를 최소힙(MinHeap) 이라고 한다.

따라서, MaxHeap은 담긴 수 중 최대값을 바로 알 수 있고 최대값을 pop할 수 있다.

또한 MinHeap은 담긴 수 중 최소값을 바로 알 수 있고 최소값을 pop할 수 있다.

PriorityQueue를 이용하여 MaxHeap과 MinHeap을 만드는 방법은 세가지 방법이 있다.

방법 1.

기본생성자 PriorityQueue()를 사용하면 MinHeap이 되고 역순으로 비교하는 comparator를 사용하면 MaxHeap이 된다.

Collections.reverseOrder()가 제공되고, 대신 custom comparator를 사용할 수 있는 생성자에서는 initial capacity도 함께 지정해야 한다.

private PriorityQueue minHeap = new PriorityQueue();
private PriorityQueue maxHeap = new PriorityQueue(10, Collections.reverseOrder());

방법2.  comparator 직접 구현하여 사용

// initialize maxheap and minheap with appropriate comparators
static PriorityQueue
 minheap = new PriorityQueue<>();
static PriorityQueue maxheap = new PriorityQueue<>(100000, myMaxHeapComparator);
//comparators for PriorityQueue
static maxHeapComparator myMaxHeapComparator = new maxHeapComparator();
//Comparator for the maxHeap, largest number has the highest priority
static class maxHeapComparator implements Comparator<Integer>{
	@Override
	public int compare(Integer i, Integer j) {
		if(i>j){
			return -1;
		}else if(i<j){
			return 1;
		}
		return 0;
	}	
}

방법3. MaxHeap값에 -1을  곱해서 반대로 풀이한다.

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();//기본값
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>();//-1 해줘서 넣어줘야함

문제풀이

Heap의 성질을 이용하여 중앙값보다 작을 값들은 MaxHeap에, 중앙값보다 큰 값들은 MinHeap에 넣어준다.

1. 일단 처음에 왼쪽부터(MaxHeap) 넣는다.

2. 오른쪽(MinHeap)이 비어있거나, 오른쪽의 최소값보다 작은 값이 들어올 경우 MaxHeap에 넣어준다.

3. MaxHeap과 MinHeap의 사이즈를 공평하게 해준다.

3-1. MaxHeap의 사이즈가 MinHeap의 사이즈보다 2개 이상 많을 때 MaxHeap의 top값을 MinHeap으로 이동시켜준다.

3-2. MinHeap의 사이즈가 MaxHeap의 사이즈보다 커질 때는 MinHeap의 top값을 MaxHeap으로 이동시켜준다.

4. 홀수번째 수가 주어질 때마다 MaxHeap의 Top값을 출력한다.