임의의 자료에서 최소값 또는 최대값을 구할 경우 가장 적합한 자료구조는? | [계리직 컴퓨터일반] 08년 1회차 기출문제 상세 페이지

최소값이나 최대값을 구하는 데 가장 적합한 자료구조는 힙(heap)이다.
힙은 완전 이진 트리로 루트에 항상 최소값(최소 힙) 또는 최대값(최대 힙)이 있어 $O(1)$에 꺼내 볼 수 있고, 삭제·삽입도 $O(\log n)$이다.
이진탐색트리: 가장 왼쪽·오른쪽 노드를 찾아가야 하며 편향되면 $O(n)$까지 걸린다.
스택: 후입선출 구조로 최소·최대값을 찾으려면 전체를 훑어야 한다.
해쉬: 키로 바로 찾는 탐색용이며 값의 크기 순서를 유지하지 않는다.