순서의 기준 정하기
작업 A, B, C가 순서대로 들어와도 B의 우선순위가 가장 높다면 B가 먼저 나올 수 있다. 숫자가 작을수록 우선인지 클수록 우선인지도 정의해야 한다. 단순한 선입 선출 큐와 다른 점은 원소를 선택하는 규칙이다.
인터페이스와 구현
우선순위 큐는 어떤 연산을 제공하고 어떤 결과를 내야 하는지 정한다. 배열이나 정렬된 목록, 여러 종류의 힙으로 구현할 수 있으며 각 연산의 비용은 다르다. 한 구현의 성능을 추상적 자료형 전체의 유일한 성능으로 일반화해서는 안 된다.
동점 처리
우선순위가 같은 두 원소 중 어느 것을 먼저 꺼낼지는 별도로 정해야 한다. 들어온 순서를 유지하려면 순번을 추가 비교 기준으로 쓰는 등의 장치가 필요하다. 우선순위가 있다는 사실만으로 동점 순서까지 결정되지는 않는다.
우선순위가 바뀌는 경우
저장된 원소의 우선순위를 바꾸는 연산이 필요한지에 따라 구현 선택이 달라진다. 일부 구현은 키 갱신을 직접 지원하고 다른 구현은 새 항목을 넣은 뒤 오래된 항목을 무시하는 방법을 사용할 수 있다. 중복과 오래된 항목을 어떻게 처리하는지도 설계의 일부다.