← 질문 목록
#238깊이 0
우선순위 큐를 힙으로 구현하는 이유는 무엇인가?
답변 연습
내 답변 적어보기접힘
이 브라우저에 자동 저장 · 0자
모범답안 확인하기내 답변 뒤에 열어보세요
정렬해 두면 넣을 자리를 만드느라 O(N)이 들고, 정렬하지 않으면 넣기는 싸지만 가장 급한 것을 찾는 데 O(N)이 든다. 어느 쪽이든 한 곳에서 값을 치른다.
| 힙 종류 | 부모·자식 관계 |
|---|---|
| 최대 힙 | 부모가 자식보다 항상 크거나 같다 |
| 최소 힙 | 부모가 자식보다 항상 작거나 같다 |
힙은 완전 이진 트리 구조를 사용한다. 완전 이진 트리라 삽입과 삭제가 모두 O(log N)이다.
반면 정렬된 배열은 삭제는 빠르지만 삽입 시 데이터 이동이 O(N)만큼 필요하다. 정렬되지 않은 배열은 삽입은 빠르지만 최댓값/최솟값을 찾는데 O(N)이 걸린다.
다익스트라 알고리즘이나 OS의 스케줄러처럼 우선순위가 계속 바뀌는 환경에서 힙을 선택한다.