힙, 우선순위 큐

image.png 힙이란 > 이진 검색 트리와 비슷한 형태의 구조를 가지고 있지만 트리보다 더 느슨한 대소 관계 조건을 가지고 있고 더 엄격한 모양 조건을 가지고 있는 구조를 말한다. 이진 검색 트리는 루트보다 작은 노드는 왼쪽 자식, 큰 노드는 오른쪽 자식의 규칙을 가지고 있는데, 힙은 부모 노드보다 자식 노드가 작기만 하면 된다. 이렇게 느슨한 대소...

image.png 문제 파악 > 새로운 원소가 주어졌을 때 컨테이너의 크기를 늘리면서 중간값을 찾고 그 중간값의 합을 계산하는 문제이다. 처음 생각했을 땐 힙에 값을 push하면 자동으로 정렬이 되니 중간 인덱스의 원소를 반환하면 된다고 생각했다. 그러나 힙은 최대값 또는 최소값만을 확실히 보장하고 나머지 원소들에 대해서는 부모 자식 노드간의 대소 관계만...