KOMAS

[자바] PriorityQueue  우선순위 큐

• 우선순위 큐
• 시간 복잡도 O(logN)
• 자바 코드

우선순위 큐

자바에는 자료구조 heap을 구현한 우선순위 큐 클래스가 있다.

큐를 생각해보면 가장 먼저 들어온 요소가 가장 먼저 나가게 되는데, 우선순위 큐에서는 요소들이

우선순위를 가져서 들어온 순서와 상관없이 우선순위가 높은 요소가 큐에서 가장 먼저 나가게 된다.

이때 나오는 요소는 우선순위가 가장 높은 heap 자료구조의 최상단 root node이다.

heap 자료구조는 가장 적은 값이나 가장 큰 값을 항상 최상단 root node에 위치시켜 이 값을 내보내는 자료구조이다.

우선순위가 가장 적은 값을 root node로 두면 최소 힙, 우선순위가 가장 높은 값을 root node로 두면 최대 힙이다.

• 중복값을 허용한다.
• 완전이진트리이다.

우선순위큐는 배열로 구현할 수 있다.

부모 node index = (index - 1) / 2

자식 node index = index * 2 + 1 ,  index * 2 + 2

우선순위 큐의 시간 복잡도

우선순위 큐에서의 시간 복잡도는 삽입, 삭제 시 O(logN)의 시간이 걸린다.

삽입시 가장 마지막 위치에 요소를 추가시킨 후 부모 노드와의 비교 후 Swap 과정을 통해 알맞은 위치를 찾아간다.

upHeap

삭제 시 root node를 반환 후 가장 마지막 요소를 root node에 위치시킨 후 자손과의 비교를 통해 Swap 과정을 거쳐

알맞은 위치를 찾아간다. 

자손과의 Swap은 둘 중 우선순위가 큰 node와 Swap한다.

downHeap

큐와 비슷한 성질을 이용하지만, 큐에서는 front 요소의 반환 시간은 O(1)이다. 하지만 우선순위 큐에서는 가장 우선순위가

높은 값을 가져온 후 완전 이진트리로 다시 만드는 과정인 Swap 과정 때문에 O(logN)이 걸린다.

자바 코드

import java.util.*;   public class PriorityQueueT{     public static void main(String[] args) {         Queue<Integer> pq= new PriorityQueue<>();         pq.offer(1);         pq.offer(2);         pq.offer(3);         pq.offer(4);           System.out.println(pq);         System.out.println(pq.poll());           Queue<Integer> pqr= new PriorityQueue<>(Collections.reverseOrder());         pqr.offer(1);         pqr.offer(2);         pqr.offer(3);         pqr.offer(4);           System.out.println(pqr);         System.out.println(pqr.poll());             Queue<Item> qi= new PriorityQueue<>();         qi.offer(new Item(1,"가"));         qi.offer(new Item(3,"나"));         qi.offer(new Item(0,"다"));         qi.offer(new Item(2,"라"));         qi.offer(new Item(4,"마"));           System.out.println(qi);         System.out.println(qi.poll());       } }   class Item implements Comparable<Item>{     int number;     String name;       Item(int number, String name){         this.number = number;         this.name = name;     }     @Override     public int compareTo(Item i){         return this.number - i.number;     }       @Override     public String toString(){         return number +" "+ name;     } }   Colored by Color Scripter

cs

 

 

우선순위 큐를 사용하는 PriorityQueue 클래스를 이용하여 1, 2, 3, 4 요소를 넣었다.

각각 최소 힙을 사용하는 pq와 최대 힙을 pqr을 코드를 작성하고 결과를 봤다.

기본형이 아닌 객체 간의 비교를 통해 우선순위 큐를 이용하는 방법은

Item Class를 작성하여 Comparable 인터페이스를 구현하여 compareTo 함수를 통해 비교 후 

Item Class의 인스턴스 필드인 number를 통해 우선순위 큐의 최소 힙을 사용했다.