모든 순서가 필요한가
모은 항목을 처음부터 끝까지 순서대로 볼 목적이라면 정렬이 자연스러운 선택일 수 있다. 반면 실행 중 새 작업이 들어오고 매번 다음 작업 하나만 고르면 우선순위 큐를 검토할 수 있다. 둘 다 순서와 관련되지만 필요한 연산이 다르다. 사용 패턴을 먼저 정해야 자료구조의 비용을 비교할 수 있다.
힙의 부분적인 순서
최소 힙은 부모가 자식보다 크지 않다는 조건을 유지해 맨 위에서 최솟값을 찾는다. 배열로 표현된 힙의 나머지 항목까지 전체 정렬 순서로 놓였다고 보장되지는 않는다. 내부 배열을 그대로 순회해 정렬된 결과라고 읽으면 안 된다. 최우선 항목을 꺼내는 연산이 어떤 조건을 다시 유지하는지 이해해야 한다.
동률의 처리
우선순위가 같은 두 작업 가운데 먼저 접수한 것을 먼저 처리하려면 그 규칙을 별도로 표현해야 한다. 자료구조의 이름만으로 동률 순서가 정해지는 것은 아니다. 비교할 수 없는 작업 객체를 우선순위와 함께 넣는 경우에도 동률 때 무엇을 비교하는지 확인한다. 접수 순번 같은 보조 기준은 요구에 따라 설계한다.
우선순위가 바뀌는 경우
큐에 들어간 항목의 우선순위 값을 외부에서 바꾸기만 하면 힙의 조건이 깨질 수 있다. 갱신 연산을 지원하는지, 기존 항목을 무효화하고 새 항목을 넣을지 등 구현 방식을 검토한다. 후자의 방식에서는 무효 항목을 실제로 꺼냈을 때 건너뛰고 정리하는 절차가 필요할 수 있다. 논리적 작업 수와 저장된 항목 수를 구분한다.
검증할 조건
빈 큐에서 꺼내는 경우, 동률이 많은 경우와 작업이 취소되는 경우를 확인한다. 매번 전체를 정렬하는 방법과 작은 입력에서 결과를 비교하면 우선순위 규칙을 검토하기 쉽다. 실무에서는 이론적인 연산 수뿐 아니라 항목 크기와 갱신 빈도, 메모리 사용량을 함께 비교해야 한다.
관련 문서
알고리즘 / 정렬 안정성과 정렬 키 / 배열