문제 파악
새로운 원소가 주어졌을 때 컨테이너의 크기를 늘리면서 중간값을 찾고 그 중간값의 합을 계산하는 문제이다. 처음 생각했을 땐 힙에 값을 push하면 자동으로 정렬이 되니 중간 인덱스의 원소를 반환하면 된다고 생각했다. 그러나 힙은 최대값 또는 최소값만을 확실히 보장하고 나머지 원소들에 대해서는 부모 자식 노드간의 대소 관계만 정의될 뿐 중간 원소들 간의 대소 관계는 확실히 보장되지 않는다.
따라서 힙을 그대로 사용할 순 없고 트립을 사용하거나 힙을 조작해서 사용해야 한다.
문제 풀이
힙은 최대값과 최소값을 효율적으로 구해 주는 자료 구조이다. 힙 안에 원소를 순서에 상관 없이 넣기만 해도 힙은 logN의 시간복잡도만으로 최대, 최소 원소를 루트로서 가지고 있다. 따라서 힙을 활용해 중간값을 구하기 위해서는 주어진 값들을 큰 값들은 최소힙에 작은 값들은 최대힙으로 절반씩 나누어 그 경계에 있는 값들을 구하면 된다.
최대힙의 크기가 최소힙보다 1만큼 더 크거나 같게끔 하면 중간값은 항상 최대힙에 포함된다. 새로운 값이 들어오면 최대힙이 1더 큰 경우엔 최소힙에, 최소힙과 최대힙이 크기가 같은 경우엔 최대힙에 넣는다. 힙의 연산처럼 일단 모양 규칙을 맞춘 뒤 대소 관계 규칙에 대해 생각하는 것이다. 새로 최대힙이나 최소힙에 들어간 값은 힙의 구조를 다시 이루는 과정에서 올바르지 않은 원소가 들어온 경우 루트로 가게된다. 루트로 가게된 원소를 반대 힙의 루트와 비교해서 최대힙의 최대 원소가 최소힙의 최소 원소보다 큰 경우 위치를 바꿔주기만 하면 된다.
느낀점
C++에서 힙은 priority_queue 클래스와 호환하여 쓸 수 있다. priority_queue에 대해서는 추가 학습 필요. 힙은 최대와 최소를 효율적으로 찾아줄 수 있는 자료 구조이다. 힙은 트리처럼 구조체와 포인터를 사용하지 않고 컨테이너 하나로 표현할 수 있으므로 같은 구조여도 트리 기반 자료 구조에 비해 속도가 두세배까지 빠르다.
