전체태그 보기

# (2개의 포스트)

doontagi

힙 - 문제1 변화하는 중간 값

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

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