[자료구조] Priority Queue (우선순위 큐)

Queue는 먼저 들어간 데이터가 먼저 나오는 형식이나, Priority Queue는 이와 다르게 데이터를 꺼낼 때 우선순위가 가장 높은 것부터 나오게 된다. 일반적인 큐처럼 추가/삭제 연산이 있지만, 그 순서에 관계없이 우선순위를 고려하여 데이터를 가져올 수 있다. 

 

Priority Queue는 힙 구조(트리구조)를 이용해서 만들고, 큰 값이 우선이 되는 최대힙과 작은 값이 우선이 되는 최소힙이 있다고 생각하면 된다. (default = 최소 힙)

 

 

🕹️ Priority Queue 사용법

• 최소 힙 (최솟값부터 배열)

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

• 최대 힙 (최댓값부터 배열)

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(((o1, o2) -> o2-o1));

 

📍 자료형 대신 내가 만든 class 형태를 사용하면

public class Main{

	public static class Student implements Comparable<Student> {
    
        String name;
        int age;

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

        @Override
        public String toString() {
            return "이름 : " + name + ", 나이 : " + age;
        }   
        
        @Override
        public int compareTo(Student stud) {
        	return this.age <= stud.age ? 1 : - 1;
            // return this.age-stud.age; // 결과는 나이가 적은 순부터 출력됨
    	} 
    }
    
	public static void main(String[] args){
    	PriorityQueue<Student> pq = new PriorityQueue<Student>();
        
        pq.add(new Student("김고앵", 12));
        pq.add(new Student("이고앵", 15));
    }
}

 

⛔️ this.age-stud.age 로 작성한다면 계산 결과가 자료형 범위를 넘어서지 않도록 (OverFlow) 주의해야 한다 !

 

 

 

Comparable & Comparator 란?

객체를 비교할 수 있게 해주는 인터페이스이다. 

 

docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html#method.summary

Comparable (Java Platform SE 8 )

Comparable 인터페이스에 compareTo(T o) 메서드가 선언되어있어 이 메소드를 Override 해야한다. 

 

docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#method.summary

Comparator (Java Platform SE 8 )

Comparator 인터페이스에 compare(T o1, T o2) 메서드가 선언되어있고 이 메소드만 Override해서 구현해주면 된다. 

 

 

이러한 인터페이스를 사용하는 이유는 클래스 객체에 있는 값들을 쉽게 비교할 수 있도록 만들기 위해서이다. 

primitive type은 부등호로 그냥 비교 가능하겠지만, 학번과 나이 정보를 갖고 있는 학생들을 비교하는 것은 어떤 것을 기준으로 우선순위를 갖게 되는지 알 수 없다. 이 문제점을 해결하기 위해 Comparator 또는 Comparable 인터페이스를 사용한다. 

 

 

Comparable& Comparator차이점 

• Comparable : 자기 자신과 매개변수 객체를 비교한다.
• Comparator : 두 매개변수 객체를 비교한다. 

👉 비교 대상이 다르고, Comparator는 Comparable과 다르게 util 패키지에 있어 import 해줘야 한다. 

 

 

Comparable

class Student implements Comparable<Student> {
 
	int age;			// 나이
	int classNumber;	// 학급
	
	Student(int age, int classNumber) {
		this.age = age;
		this.classNumber = classNumber;
	}
	
	@Override
	public int compareTo(Student o) {
    
		// 자기자신의 age가 o의 age보다 크다면 양수
		if(this.age > o.age) {
			return 1;
		}
		// 자기 자신의 age와 o의 age가 같다면 0
		else if(this.age == o.age) {
			return 0;
		}
		// 자기 자신의 age가 o의 age보다 작다면 음수
		else {
			return -1;
		}
        
        
        /*
		 * 만약 자신의 age가 o의 age보다 크다면 양수가 반환 될 것이고,
		 * 같다면 0을, 작다면 음수를 반환할 것이다.
		 */
		//return this.age - o.age;
	}
}

자기 자신과 상대를 비교한다. this는 객체 자신을 나타내고, o는 다른 객체를 나타낸다. 

 

---

Comparator

import java.util.Comparator;	// import 필요

class Student implements Comparator<Student> {
 
	int age;			// 나이
	int classNumber;	// 학급
	
	Student(int age, int classNumber) {
		this.age = age;
		this.classNumber = classNumber;
	}
	
	@Override
	public int compare(Student o1, Student o2) {
    
		// o1의 학급이 o2의 학급보다 크다면 양수
		if(o1.classNumber > o2.classNumber) {
			return 1;
		}
		// o1의 학급이 o2의 학급과 같다면 0
		else if(o1.classNumber == o2.classNumber) {
			return 0;
		}
		// o1의 학급이 o2의 학급보다 작다면 음수
		else {
			return -1;
		}
        
        
        /*
		 * 만약 o1의 classNumber가 o2의 classNumber보다 크다면 양수가 반환 될 것이고,
		 * 같다면 0을, 작다면 음수를 반환할 것이다.
		 */
		//return o1.classNumber - o2.classNumber;
	}
}

 

 

참고

https://st-lab.tistory.com/243