알고리즘
-
[변리사 2차-1번] 구간 히프 (Interval Heap)알고리즘 2020. 5. 25. 19:40
2019년 제 56회 변리사 2차 데이터 구조론 2교시 1번 문제 해설 1. 구간히프를 정의하고, 그 특성에 관하여 설명하시오.(5점) * 먼저 heap이란? 숫자의 최대값, 최소값을 빠르게 탐색하기 위해 고안된 완전이진트리 (Complete Binary Tree)이다. 기본적인 Heap의 각 노드는 하나의 숫자로 이루어져 있으며 삽입,삭제시 리프노드부터 시작하여 부모-자식간의 대소판별 경쟁을 통해 최소 또는 최대값이 항상 루트 노트들 차지한다. 이러한 성질 때문에 우선순위큐 (Priority Queue)는 최소,최대 힙으로 만들어져있다. * 구간 Heap? 구간 히프는 Heap과 동일한 완전이진트리의 형태면서 각각의 노드는 최대 두개의 숫자로 구성 되어있다. 노드에 적힌 두개의 숫자는 폐구간 [a,b]..