4. 저장된 원소로부터 중앙값을 구하여 반환하는 get() 함수를 작성합니다.
double get()
{
if (maxHeap.size() == minHeap.size())
return (maxHeap.top() + minHeap.top()) / 2.0;
if (maxHeap.size() < minHeap.size())
return minHeap.top();
return maxHeap.top();
}
};
5. 앞서 만든 median 구조체를 사용하는 main() 함수를 작성합니다.
int main()
{
median med;
med.insert(1);
std::cout << "1 삽입 후 중앙값: " << med.get() << std::endl;
med.insert(5);
std::cout << "5 삽입 후 중앙값: " << med.get() << std::endl;
med.insert(2);
std::cout << "2 삽입 후 중앙값: " << med.get() << std::endl;
med.insert(10);
std::cout << "10 삽입 후 중앙값: " << med.get() << std::endl;
med.insert(40);
std::cout << "40 삽입 후 중앙값: " << med.get() << std::endl;
}
이 프로그램을 실행하면 다음과 같은 출력이 나타납니다.
1 삽입 후 중앙값: 1
5 삽입 후 중앙값: 3
2 삽입 후 중앙값: 2
10 삽입 후 중앙값: 3.5
40 삽입 후 중앙값: 5
이 방법은 새로운 데이터를 추가할 때 O(log N)의 시간 복잡도를 사용하며, 이는 정렬을 이용하는 방법의 시간 복잡도 O(N log N)보다 효율적입니다.