[Java]running median 복습하면서 자바로 구현해보기

1. running median

 

우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median (tistory.com)

우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median

 

 

1) 최대힙과 최소힙 2개를 초기화

 

2) 최대힙의 원소의 수와 최소힙의 원소의 수가 동일하다면, 최대힙에 수를 넣어주고

 

3) 최대힙의 원소의 수가 최소힙의 원소의 수 + 1이라면, 최소힙에 수를 넣어준다.

 

즉 최대힙 > 최소힙 > 최대힙 > 최소힙 >....으로 번갈아가면서 수를 넣어준다.

 

4) 최대힙의 루트가 최소힙의 루트보다 크거나 같다면, 서로 교환해서, 최대힙의 루트가 항상 최소힙의 루트보다 작게 만든다

 

5) 이렇게 하면, 두 힙에 들어간 원소의 수가 홀수개이면 최대힙의 루트가 항상 수열의 중앙값이 된다.

 

 

2. 자바로 구현

 

위 알고리즘 그대로 쓰면 된다

 

주의할 점은 최대힙을 구성할때 -를 붙여서 넣어줘야하고, 빼서 사용할때는 -를 다시 붙여줘야하고

 

.peek()의 경우 힙에 원소가 0개이면 에러나므로 일단 첫 원소는 for문 밖에서 최대힙에 넣어주고 시작하자

 

최대힙 루트와 최소힙 루트를 교환할때는, poll()로 각각 빼서 최대힙에서 뺀건 최소힙에, 최소힙에서 뺀건 최대힙에 넣어주면 된다

 

import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        for(int i = 0; i < t; i++){

            int m = sc.nextInt();

            PriorityQueue<Integer> max_heap = new PriorityQueue<>();
            PriorityQueue<Integer> min_heap = new PriorityQueue<>();

            max_heap.add(-sc.nextInt());
            System.out.print(-max_heap.peek() + " ");

            for(int j = 1; j < m; j++){

                if(max_heap.size() == min_heap.size()){
                    max_heap.add(-sc.nextInt());
                } else {
                    min_heap.add(sc.nextInt());
                }

                if(-max_heap.peek() >= min_heap.peek()){
                    int max = -max_heap.poll();
                    int min = min_heap.poll();

                    max_heap.add(-min);
                    min_heap.add(max);
                }

                if (j % 2 == 0){
                    System.out.print(-max_heap.peek() + " ");
                }
            }

            System.out.println();
        }
    }
}