우선순위 큐를 힙으로 구현하는 이유는 무엇인가?

정렬해 두면 넣을 자리를 만드느라 O(N)이 들고, 정렬하지 않으면 넣기는 싸지만 가장 급한 것을 찾는 데 O(N)이 든다. 어느 쪽이든 한 곳에서 값을 치른다.

힙은 완전 이진 트리 구조를 사용한다. 완전 이진 트리라 삽입과 삭제가 모두 O(log N)이다.

반면 정렬된 배열은 삭제는 빠르지만 삽입 시 데이터 이동이 O(N)만큼 필요하다. 정렬되지 않은 배열은 삽입은 빠르지만 최댓값/최솟값을 찾는데 O(N)이 걸린다.

다익스트라 알고리즘이나 OS의 스케줄러처럼 우선순위가 계속 바뀌는 환경에서 힙을 선택한다.