Java | Priority Queue(우선순위 큐) 와 Comparable, Comparator

바다·2024년 3월 28일

Java comparable comparator priority queue

Java

목록 보기

8/18

Priority Queue (우선순위 큐)

우선순위 큐는 먼저 들어간 데이터가 먼저 나오는 일반적인 큐와는 다르게 데이터를 꺼낼 때 우선순위가 가장 높은 데이터가 가장 먼자 나온다.
우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙(클수록 먼저) 혹은 최소힙(작을수록 먼저) 을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸다.
루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮긴다

힙(Heap)이란?

최솟값 또는 최대값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조

Priority Queue의 특징 정리

높은 우선순위의 요소를 먼저 꺼내서 처리 (우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야 함)
내부 요소는 힙으로 구성되어 있어 이진트리 구조
내부구조가 힙으로 구성되어 있기 때문에 시간복잡도는 O(NlogN)

Priority Queue의 우선순위 기준 부여하기

java.lang.Comparable : 원소 스스로 다른 원소와 자신을 비교할 때 사용하는 방법
- compareTo 메소드를 구현해야 함
- 자기 자신과 매개변수 객체를 비교
java.util.Comparator : 두 개의 원소 대소 비교를 비교자가 판단하는 방법
- compare 메소드를 구현해야 함
- 두 매개변수 객체를 비교

Comparable

"자기 자신과 매개변수 객체를 비교"

int compareTo(T other) : 비교, 판단 결과를 int형으로 줌
자기 자신 - other 형태
- 음수 : 앞이 더 작다는 의미
- 양수 : 앞이 더 크다는 의미
- 0 : 두 개의 원소가 같은 경우

기본구조

public class ClassName implements Comparable<Type> {
    
    //code
    
    @Override
    public int compareTo(Type o) {
        // 비교 구구현
    }
}

간단한 예제

유저 이름 사전 순으로 정렬

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

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

    @Override
    public int compareTo(User o) {
        int result = this.name.compareTo(o.name);
        return result;
    }
}

유저 나이로 정렬

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

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

    @Override
    public int compareTo(User o) {
        if(this.age > o.age) {
            return 1;
        } else if(this.age == o.age) {
            return 0;
        } else {
            return -1;
        }
    }
}

유저 이름 사전순으로 정렬, 만약 이름이 같을 경우 나이순으로 정렬

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

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

    @Override
    public int compareTo(User o) {
        int result = this.name.compareTo(o.name);
        if(result == 0) {
            res = this.age - o.age;
        }
        
        return result;
    }
}

Comparator

"두 매개변수 객체를 비교"

int compare(T o1, T o2)
o1 - o2의 형태
- 음수 : 앞이 더 작다는 의미 (오름차순으로 만들고 싶을 때)
- 양수 : 앞이 더 크다는 의미 (내림차순으로 만들고 싶을 때)

기본구조

import java.util.Comparator;
import java.util.PriorityQueue;

// 클래스에서 사용할 때
public static class ClassName implements Comparator<Type> {
    @Override
    public int compare(Type o1, Type o2) {
        return o1 - o2;
    }
}

// Priority Queue에서 사용할 때

PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
});

간단한 예제

유저 이름으로 오름차순 정렬

import java.util.Comparator;
import java.util.PriorityQueue;

// Priority Queue에서 사용할 때
PriorityQueue<User> queue = new PriorityQueue<User>(new Comparator<User>() {
    @Override
    public int compare(User o1, User o2) {
        return o1.name - o2.name? 1 : -1;
    }
});

유저 나이로 오름차순 정렬

import java.util.Comparator;
import java.util.PriorityQueue;

// Priority Queue에서 사용할 때
PriorityQueue<User> queue = new PriorityQueue<User>(new Comparator<User>() {
    @Override
    public int compare(User o1, User o2) {
        return o1.age - o2.age? 1 : -1;
    }
});

유저 이름으로 오름차순 정렬하고, 이름이 같을 때 나이로 정렬

import java.util.Comparator;
import java.util.PriorityQueue;

// Priority Queue에서 사용할 때
PriorityQueue<User> queue = new PriorityQueue<User>(new Comparator<User>() {
    @Override
    public int compare(User o1, User o2) {
        int result = o1.name - o2.name;
        if(result == 0) {
            result = o1.age - o2.age;
        }
        return result;
    }
});