[Algorithm] 23 우선순위 큐와 힙 - 3

23.3 문제: 변화하는 중간 값

한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다.

예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이고, 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의한다.

한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있다.

텅 빈 수열에서 시작해서 각 수가 추가될 때마다 중간값을 계산하는 프로그램을 작성하세요.

예를 들어 3, 1, 5, 4, 2 순서대로 숫자가 추가될 경우 수열의 중간값은 3, 1, 3, 3, 3 순서로 변화합니다.

입력 생성

• A[0] = 1983

• A[i] = (A[i-1] * a + b) % 20090711

  a와 b는 입력에 주어지는 상수입니다.

10 1 0
A[0] = 1983
A[1] = (1983 * 1 + 0) mod 20090711 = 1983
A[2] = (1983 * 1 + 0) mod 20090711 = 1983
A[3] = (1983 * 1 + 0) mod 20090711 = 1983
A[4] = (1983 * 1 + 0) mod 20090711 = 1983
A[5] = (1983 * 1 + 0) mod 20090711 = 1983
A[6] = (1983 * 1 + 0) mod 20090711 = 1983
A[7] = (1983 * 1 + 0) mod 20090711 = 1983
A[8] = (1983 * 1 + 0) mod 20090711 = 1983
A[9] = (1983 * 1 + 0) mod 20090711 = 1983
=> 19830

10000 1273 4936
A[0] = 1983
A[1] = (1983 * 1273 + 4936) mod 20090711 = 2,529,295

num	ordered	median
3	3	3
1	1, 3	1
5	1, 3, 5	3
4	1, 3, 4, 5	3
2	1, 2, 3, 4, 5	2

---
  1
 2 5
3 4
---

출력

N 개의 중간 값의 합을 20090711 로 나눈 나머지를 출력

풀이 방법

• 균형 잡힌 이진 트리 검색을 사용

  트립을 사용하면 새 원소를 추가하는 작업과 k 번째 원소를 찾는 작업을 모두 O(logN)에 할 수 있다.

    int runningMedian(int n, RNG rng){
    	Node* root = NULL;
    	int ret = 0;
    	for(int cnt = 1, cnt <= n; ++cnt){
    		root = insert(root, new Node(rng.next());
    		int median = kth(root, ( cnt + 1 ) / 2 ) -> key;
    		ret = (ret + median) % 20090711;
    	}
    	return ret;
    }
  

• 주어진 수열을 두 묶음으로 나누어 풀이하는 방법

  숫자들을 정렬한 뒤 앞의 절반을 최대 힙에, 뒤의 절반을 최소 힙에 넣는다.

  만약, 수열의 길이가 홀수라면 최대 힙에 숫자를 하나 더 넣도록 한다.

  1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.
  2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다.

  이 수열의 중간 값은 항상 최대 힙의 루트에 존재하게 된다.

    int runningMedian(int n, RNG rng){
    	priority_queue<int, vector<int>, less<int>> maxHeap;
    	priority_queue<int, vector<int>, greater<int>> minHeap;
    	int ret = 0;
    	// 반복문 불변식;
    	// 1. maxHeap 의 크기는 minHeap 의 크기와 같거나 1 더 크다.
    	// 2. maxHeap.top() <= minHeap.top()
    	for(int cnt = 1, cnt <= n; ++cnt){
    		// 우선 1번 불변식부터 만족시킨다.
    		if(maxHeap.size() == minHeap.size())
    			maxHeap.push(rng.next());
    		else
    			minHeap.push(rng.next());
    		// 2번 불변식이 깨졌을 경우 복구하자.
    		if(!minHeap.empty() && !maxHeap.empty() && minHeap.top() < maxHeap.top()){
    			int a = maxHeap.top(), b = minHeap.top();
    			maxHeap.pop(); minHeap.pop();
    			maxHeap.push(b);
    		  minHeap.push(a);
    		}
    		ret = (ret + maxHeap.top()) % 20090711;
    	}
    	return ret;
    }
  

  nums	cnt	maxHeap.size() == minHeap.size()	maxHeap	minHeap	minHeap.top() < maxHeap.top()	maxHeap	minHeap
  1, 2, 3, 4, 5, 6, 7, 8	1	true	1
  	2	false	1	2
  	3	true	1, 3	2	true	1, 2	3
  	4	false	1, 2	4, 3
  	5	true	1, 2, 5	4, 3	true	1, 2, 4	5, 4

  ### 수열 생성하기

  난수 생성기로 입력을 생성한다.

  선형 합동 난수 생성기

    struct RNG {
    	int seed, a, b;
    	RNG(int _a, int _b) : a(_a), b(_b), send(1983) {}
    	int next() {
    	int ret = seed;
    	seed = (( seed * (long long)a ) + b) % 20090711;
    	return ret;
    }