[DataStructure] Priority Queue(우선 순위 큐) feat. JAVA

Priority Queue

PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.

Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출 해준다.

PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이다.

데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행된다.
최대 값이 우선순위인 큐 = 최대 힙, 최소 값이 우선순위인 큐 = 최소 힙

 

Priority Queue 특징

• 우선순위 큐는 값을 비교해야하므로 null을 허용하지 않는다.
• 마찬가지로 비교할 수 없는 객체는 큐를 만들 수 없다.
• 내부구조는 이진트리 힙으로 구성되어 있다.
• 내부구조가 이진트리로 되어있어서 add() 및 poll() 메서드(추가, 삭제 메서드) 0(log(n)) 시간이 걸린다.
• AbstractQueue , AbstractCollection , Collection 및 Object클래스에서 메서드를 상속한다.

 

Priority Queue 선언

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);

 

Priority Queue Add (값 추가)

priorityQueueLowest.add(1);
priorityQueueLowest.add(10);
priorityQueueLowest.offer(100);

priorityQueueHighest.add(1);
priorityQueueHighest.add(10);
priorityQueueHighest.offer(100);

 

Priority Queue remove (값 제거)

// 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.poll();

// 첫번째 값 제거 비어있다면 예외 발생
priorityQueueLowest.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueueLowest.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueueLowest.element();

// 초기화
priorityQueueLowest.clear();

 

 

참고

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

[Java] Priority Queue(우선 순위 큐)

https://crazykim2.tistory.com/575#text2

[JAVA] Priority Queue(우선순위 큐) 개념 및 사용법 정리