[Java] Priority Queue Method, 사용법

Priority Queue ?

Priority Queue(우선순위 큐)는 일반적인 큐의 구조(FIFO)를 가진다.

'우선순위' 라는 것을 활용해 데이터에 의미를 부여하고 그에 따라 큐가 작동하는 자료구조이다.

즉, 우선순위가 높은 데이터가 먼저 나간다.

Priority Queue의 특징

우선순위를 지정해줄 수 있다.

내부 요소는 Heap으로 구성되어 Binary Tree 구조이다.

시간 복잡도는 O(NlogN)이다.

Queue에 들어갈 데이터의 형태에 따라 다른데, 사용자가 선언한 Class의 객체라면

사용자가 해당 Class에서 Comparable Interface를 구현해서 Override 해줘야 Priority Queue에 넣고 사용할 수 있다. 

 

---

Priority Queue Declaration

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 수 우선 순위
PriorityQueue<Integer> pq = new PriorityQueue<>();

//높은 수 우선 순위
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());

 

---

Priority Queue Method

 

• add(value), offer(value)
• peek()
• element()
• poll()
• remove()
• clear()
• size()
• contains(value)
• isEmpty()
• toArray(), toArray(T[] a)

1. value 추가

   add(value) , offer(value)

pq.add(10);
pq.offer(1000);

 

value 가 Priority Queue에 추가된다.

 

---

2. value 반환

peek()

int value = pq.peek();
// queue에서 가장 우선순위가 높은 데이터 반환
// 만약 비어있다면 null return

element()

int value = pq.element();
// queue에서 가장 우선순위가 높은 데이터 반환
// 만약 비어있다면 예외 발생

 

---

3. value 반환 & 삭제

poll()

int value = pq.poll();
// queue에서 가장 우선순위가 높은 데이터 반환하면서 그 데이터 queue에서 삭제
// 만약 비어있다면 null return

remove()

int value = pq.remove();
// queue에서 가장 우선순위가 높은 데이터 반환하면서 그 데이터 queue에서 삭제
// 만약 비어있다면 예외 발생

 

---

4. Priority Queue 초기화

clear()

pq.clear();

 

---

5. User Class Use Example

Comparable Interface 구현 - compareTo(obfect o) operation 작성

class Task implements Comparable<Task> {
    public int index;
    public int start;
    public int processing;

    public Task(int i, int s, int p) { // 생성자
        index = i;
        start = s;
        processing = p;
    }
    @Override
    public int compareTo(Task task) {
        if (this.processing > task.processing) // 오름차 순
            return 1;
        else if (this.processing < task.processing)
            return -1;
        else { // processing 같다면 인덱스 오름차 순
            if(this.index > task.index) return 1;
            else return -1;
        }
    }
}

위의 예에서는 Class 멤버변수 processing과 index를 기준으로 우선순위를 정했다.

processing이 낮으면 낮을수록 우선순위가 높아지게 된다.

processing이 같을 경우, index를 비교한다.

index가 낮으면 낮을수록, 우선순위가 높아지게 된다.

 

---

6. 그 외 Method

 

size()

queue에 들어있는 데이터의 개수를 반환해준다.

int size = pq.size();

 

contains(value)

queue에 해당 value가 들어있는지 아닌지 확인해준다.

queue가 가지는 data-type을 value로 넣어야 한다.

  들어있으면 - true

  안 들어있으면 - false

pq.add(10);
pq.add(100);

if(pq.contains(10)){
	System.out.println("10이 들어있음");
}
else {
	System.out.println("10이 없음");
}

 

isEmpty()

queue가 비어있는지 확인해준다.

  비어있으면 - true

  데이터가 있으면 - false

if(pq.isEmpty){
    System.out.println("비어있음");
}
else {
    System.out.println("비어있지 않음");
    pq.clear(); // 비우기
}

 

toArray(), toArray(T[] a)

Queue에 들어있는 데이터들을 Array로 반환해준다.

// pq의 data-type이 Integer라고 가정

// ex.1
Object[] arr = pq.toArray();

// ex.2
Integer[] arr = new Integer[5];
pq.toArray(arr);

// ex.3
// arr, arr2 두 배열이 같은 값을 가지게 됨
Integer[] arr = new Integer[5]; // Queue의 크기보다 커서 남으면 남은 자리는 null로 채워짐
Integer[] arr2 = pq.toArray(arr);

Queue에 들어있는 데이터들이 Array로 옮겨진다.

여기서 Array로 옮겨지는 순서는 어떻게 될까?

Queue가 가지고 있는 내부구조인 Heap의 모양대로 옮겨지게 된다.