[트리] RUNNINGMEDIAN 변화하는 중간값

1. 균형잡힌 이진 검색트리를 이용한 풀이

 

트립 을 구현하여 수열이 추가될때마다 이진 검색트리를 유지 시키고,

 

k번째 수열을 찾는 kth함수를 구현하여 중간값을 찾는다. 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct NODE {
    int priority;
    int key, size;
    NODE *right, *left;
    NODE(const int& _key): key(_key), priority(rand()), size(1), right(NULL), left(NULL) {}
    void calcSize() {
        size = 1;
        if(right) size+=right->size;
        if(left) size+=left->size;
    }
    void setLeft(NODE* node) {
        left = node;
        calcSize();
    }
    void setRight(NODE* node) {
        right = node;
        calcSize();
    }
};
typedef pair<NODE*, NODE*> CHILDPAIR;
 
CHILDPAIR split(NODE* root, int key) {
    if(root == NULL) return CHILDPAIR(NULL, NULL);
    if(root->key < key) {
        CHILDPAIR rs = split(root->right, key);
        root->setRight(rs.first);
        return CHILDPAIR(root, rs.second);
    }
    CHILDPAIR ls = split(root->left, key);
    root->setLeft(ls.second);
    return CHILDPAIR(ls.first, root);
}
NODE* insert(NODE* root, NODE* node) {
    if(root == NULL) return node; 
    if(root->priority < node->priority) {
        CHILDPAIR child = split(root, node->key);
        node->setLeft(child.first);
        node->setRight(child.second);
        return node;
    }
    if(root->key < node->key) 
        root->setRight(insert(root->right, node));
    else
        root->setLeft(insert(root->left, node));
    return root;
}
NODE* merge(NODE* left, NODE* right) {
    if(left == NULL) return right;
    if(right == NULL) return left;
    if(left->priority < right->priority) {
        right->setLeft(merge(left, right->left));
        return right;
    }
    left->setRight(merge(left->right, right));
    return left;
}
NODE* erase(NODE* root, int key) {
    if(root == NULL) return NULL;
    if(key == root->key) {
        NODE* ret = merge(root->left, root->right);
        delete root;
        return ret;
    }
    if(key < root->key) {
        root->setLeft(erase(root->left, key));
    }
    else 
        root->setRight(erase(root->right, key));
    return root;
}
 
NODE* kth(NODE* tree, int k) {
    int leftSize = tree->left == NULL ? 0: tree->left->size;
    if(leftSize + 1 == k) return tree;
    if(leftSize < k) return kth(tree->right, k - leftSize - 1);
    return kth(tree->left, k);
}
 
 
 
int testCase = 0;
int N;
int a, b;
const int MOD = 20090711;
 
int A(int i, const int* before = NULL)
{
    if(i == 0) return 1983;
    if(before==NULL)
        return ((A(i-1)* (long long)a)%MOD + b )%MOD;
    return (((*before) * (long long)a)%MOD + b )%MOD;
}
 
int median() {
    int ret = 0;
    int before = 1983;
    NODE* tree = NULL;
    for(int i = 0; i < N; i++) {
        NODE* node = new NODE(A(i, &before));
        tree = insert(tree, node);
        ret =  (ret+kth(tree, i/2 + 1)->key)%MOD;
        before = node->key;
    }
    return ret;
}
//N median... even=> smaller
int main()
{
    cin>>testCase;
    while(testCase--)
    {
        cin>>N>>a>>b;
        cout<<median()<<"\n";
    }
}

 

2. 우선순위 큐를 이용한 풀이

 

수열을 절반으로 최대힙 | 최소힙으로 분리시킨다.

 

그러면 최대힙의 최대 원소가 최대값이 된다.

 

이러한 형태를 유지시키기위해서는 다음과 같은 불변식이 필요하다.

 

- 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다 (홀수인 경우)

- 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나같다.

 

책에서는 stl 인 priority_queue 를 사용하여 문제를 해결하였다.

 

priority_queue<int, vector<int>, less<int> > maxHeap;
priority_queue<int, vector<int>, greater<int> > minHeap;

maxHeap.size();
maxHeap.push(x);
maxHeap.pop();
maxHeap.top();

 

 

 

3. 실수들

 

트립구조체를 구현할 때 calcSize 에서 size = 1 이 아니라 size = 0으로 구현함.

erase를 구현할 때 delete를 안해줬다.

 

 

 

• RUNNINGMEDIAN