Priority Queue

Priority Queue

Priority Queue

• Queue의 item들 사이에 우선 순위가 존재하는 것
  • ex) item 값이 클수록 우선 순위가 높다
• 높은 우선 순위를 가진 요소가 언제라도 접근 가능한 위치에 존재하는 Queue
• Dequeue를 실행했을 때 우선 순위가 높은 순서대로 Dequeue
• Priority Queue 선언 방법

  // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
  PriorityQueue<Integer> pQ = new PriorityQueue<>();
   
  // 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)
  PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder()

Implement Level

• Unsorted List
  • 우선 순위가 높은 item 찾기 O(N)
  • 우선 순위가 높은 item Dequeue O(1)
  • item이 삭제된 자리가 비어 있기 때문에 뒤에 존재하는 item들 한 칸씩 앞으로 Shift O(N)
• Array-Based Sorted List
  • 우선 순위로 정렬돼 있기 때문에 item 삭제는 O(1) 삭제된 부분을 메꾸기 위해 Shift O(N)
  • Enqueue 진행하면 우선 순위에 따른 item 위치 찾기 O(N), Insert O(1), 넣을 자리 마련하기 위해 item들 뒤로 한 칸씩 Shift O(N)
• Linked Sorted List
  • Enqueue 시에 new item의 우선 순위에 따른 위치를 찾기 위해 O(N)
• Binary Tree
  • 평균적으로 item의 위치를 찾는 데 O(log N)
  • 정렬 리스트를 tree로 구현한 것처럼 tree가 선형이라면 item 위치 탐색에 O(N)
  • Enqueue와 Dequeue 모두 평균적으로 O(log N)
• Heap
  • Priority Queue를 저장하기에 제일 자연스러운 방식
  • 찾기, Enqueue, Dequeue 모두 O(log N)

Implement

• 따라서 시간이 최소로 걸리는 heap을 통해 구현되어 있음
• 아이템이 삽입되면 reHeapUp()을 통해 위치 재정렬
  • 아이템이 들어오면 일단 마지막에 삽입
  • 부모와 비교해서 우선 순위가 높다면 swqp
  • 부모보다 우선 순위가 높지 않을 때까지 반복
• 아이템이 삭제되면 reHeapDown()을 통해 위치 재정렬
  • 루트 노드와 마지막 노드 swqp
  • 마지막 노드 제거 → 루트에 있던 데이터 제거
  • 자식 노드 두 개와 루트 노드 비교한 뒤 루트 노드의 우선 순위가 낮으면 swap

Method

• add(): 우선 순위 큐에 원소 추가
  • 큐가 꽉 찬 경우 에러 발생
• offer(): 우선 순위 큐에 원소 추가
  • 값 추가 실패시 flase 반환
• poll(): 우선 순위 큐에서 첫 번째 값을 반환하고 제거, 비어 있으면 null
• remove(): 우선 순위 큐에서 첫 번째 값을 반환하고 제거, 비어 있으면 에러
• isEmpty(): 우선 순위 큐가 비어 있는지 boolean 값 반환
• cleare(): 우선 순위 큐를 초기화
• size(): 우선 순위 큐에 포함되어 있는 원소의 수를 반환

Priority Queue에 객체를 저장하고 싶을 때

• 저장하는 객체들이 Comparator의 구현체여서 비교 가능하도록 설정
• 혹은 anonymous class로 비교 가능하도록 설정