[자료구조]중간값 찾기

 

#include <iostream>
#include <vector>
#include <queue>
#include <random>

using namespace std;

struct median
{
	// priority_queue<자료형, 구현체, 비교 연산자>
	// less는 큰 수부터 출력, greater는 작은 수부터 출력
	priority_queue<int, vector<int>, less<int>> maxHeap;
	priority_queue<int, vector<int>, greater<int>> minHeap;

	// Heap에 데이터 insert
	void insert(int data) {

		// 초기값으로 max힙에 데이터를 push해준다. 
		if (maxHeap.size() == 0) {
			maxHeap.push(data);
			return;
		}

		// max힙과 min힙의 사이즈가 같다면 중간값과 비교하여 큰 데이터는 min힙에 push 작은 데이터는 max힙에 push 한다. 
		if (maxHeap.size() == minHeap.size()) {
			if (data <= get()) maxHeap.push(data);
			else minHeap.push(data);

			return;
		}

		// max힙보다 min힙의 사이즈가 클때 
		if (maxHeap.size() < minHeap.size()) {
			// push할 데이터가 중간값보다 크다면 max힙에 min힙의 최소값을 넣어주고 min힙은 최소값을 pop 시킨 후 데이터를 push한다.
			if (data > get()) {
				maxHeap.push(minHeap.top());
				minHeap.pop();
				minHeap.push(data);
			}
			// 데이터가 중간값보다 작다면 max힙에 push한다.
			else {
				maxHeap.push(data);
			}
			return;
		}

		// max힙이 min힙보다 사이즈가 크고 데이터가 중간값보다 작다면 min힙에 max힙의 최대값을 넣어주고 max힙은 최대값을 pop 시킨 후 데이터를 push한다.
		if (data < get()) {
			minHeap.push(maxHeap.top());
			maxHeap.pop();
			maxHeap.push(data);
		}
		// 데이터가 중간값보다 크다면 min힙에 push한다.
		else {
			minHeap.push(data);
		}

	}

	// Heap의 현재 중간값 리턴
	double get() {
		// max힙과 min힙의 사이즈가 같으면 max힙의 최대값과 min힙의 최소값의 평균이 중간값이 된다.
		if (maxHeap.size() == minHeap.size()) {
			return (maxHeap.top() + minHeap.top()) / 2.0;
		}
		// min힙의 사이즈가 더 크면 min힙의 최소값이 중간값이 된다.
		if (maxHeap.size() < minHeap.size()) {
			return minHeap.top();
		} 
		// max힙의 사이즈가 더 크면 max힙의 최대값이 중간값이 된다.
		return maxHeap.top();
	}
};




int main(void) {

	median myMed;

	// 난수 생성
	// 운영체제 단에서 제공하는 시드값을 얻음
	random_device rd;

	// 난수 생성 속도개선을 위해 random device를 통해 난수 생성 엔진을 초기화함.
	mt19937 gen(rd());

	// 1~100까지의 균등한 확률로 데이터를 생성함.
	uniform_int_distribution<int> dis(1, 100);

	for (int i = 1; i < 100; i++) {
		myMed.insert(dis(gen));
		cout << dis(gen) <<" 삽입 후 중앙값: " << myMed.get() << endl;
	}
	return 0;
}