[Java] Priority Queue

1. Priority Queue (우선순위 큐)

• 일반적인 큐의 구조 FIFO를 가지면서 우선순위를 먼저 결정하고 우선순위가 높은 데이터가 먼저 나가는 자료구조
• PriorityQueue에 저장할 객체는 Comparable Interface 구현 필요
• 힙을 이용하여 구현하며 이진트리 구조를 가짐
• 힙으로 구성되어 있으므로 복잡도 O(nlogn)

 

2. 사용법

PriorityQueue 생성자

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

// 작은 값이 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> pq = new PriorityQueue<>();

// 큰 값이 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> pqMax = new PriorityQueue<>(Collections.reverseOrder());

 

PriorityQueue 멤버함수

int x;

pq.add(x);	// 실패시 IllegalStateException 발생
pq.offer(x);

pq.poll();	// 첫번째 값 반환하고 제거. 비어있다면 null 반환
pq.remove();	// 비어있다면 예외 발생
pq.peek();	// 첫번째 값 반환. 비어있다면 null 반환
pq.element();	// 첫번째 값 반환. 비어있다면 예외 발생.
pq.clear();

 

3. Comparable Interface

Custom Class

class Student {
	String name;
    int age;
    
    public Student(String name, int age) {
    	this.name = name;
        this.age = age;
   	}
}

 

Comparable 이용한 priorityQueue 생성

class Student implements Comparable<Student> {
    String name;
    int age;
    
    public Student(String name, int age) {
    	this.name = name;
        this.age = age;
   	}
   	
    // 작은 값이 우선 순위 가짐
    @Override
    public int compareTo(Student o) {
    	return this.age - o.age;
    }
}

PriorityQueue<Student> pq = new PriorityQueue<>();

pq.offer(new Student("kim", 28));
pq.offer(new Student("park", 27));
pq.offer(new Student("min", 29));
// park, kim, min 순서로 우선순위 큐에 저장됨

 

Comparator 이용한 priorityQueue 생성

class Student implements Comparator<Student> {
    String name;
    int age;
    
    public Student(String name, int age) {
    	this.name = name;
        this.age = age;
   	}
}

public static Comparator<Student> ageComp = new Comparator<Student>() {
	// 큰 값이 우선순위 가짐
    @Override
    public int compare(Student s1, Student s2) {
    	return s2.age - s1.age;
    }
});

public static Comparator<Student> nameComp = new Comparator<Student>() {
	// 사전순 앞에 오는 이름이 우선 순위
    @Override
    public int compare(Student s1, Student s2) {
    	return s1.name.compareTo(s2.name);
    }
});

// 나이가 많은 순으로 정렬
PriorityQueue<Student> pq1 = new PriorityQueue<Student>(new ageComp());
pq1.offer(new Student("kim", 28));
pq1.offer(new Student("park", 27));
pq1.offer(new Student("min", 29));
// min, kim, park 순으로 우선순위 큐에 저장됨

// 알파벳 사전순으로 정렬
PriorityQueue<Student> pq2 = new PriorityQueue<Student>(new nameComp());
pq2.offer(new Student("kim", 28));
pq2.offer(new Student("park", 27));
pq2.offer(new Student("min", 29));
// kim, min, park 순으로 우선수위 큐에 저장됨