[자바/java] 우선순위 큐 정렬하기 priorityQueue sort

Heap 구조에 대해서는 tosuccess.tistory.com/31?category=853902 를 참고해주세요!

우선순위 큐는 힙(Heap)구조를 가지며, 정렬 기준에 따라 가장 큰 값이 먼저 나오는 MaxHeap을 만들 수 있고, 가장 작은 값이 나오는 MinHeap을 만들 수 있다.

 

이번에는 우선순위 큐를 정렬하는 방법에 대해 다뤄보겠다.!

 

1. 우선순위 큐 사용하기

    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
 
        priorityQueue.add(4);
        priorityQueue.add(6);
        priorityQueue.add(5);
        priorityQueue.add(1);
 
        
        while(!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());            //remove()를 사용하셔도 됩니다.
        }
    }

/*출력*/
1 4 5 6

기본적으로 정수형에 대해서는 오름차순 정렬을 합니다.

 

 

 

2. 우선순위 큐 반대로 정렬

public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
 
        priorityQueue.add(4);
        priorityQueue.add(6);
        priorityQueue.add(5);
        priorityQueue.add(1);
 
        
        while(!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());            //remove()를 사용하셔도 됩니다.
        }
    }

/*출력*/
6 5 4 1

Collections 클래스에 reverseOrder() 을 사용하여 MaxHeap구조를 만들 수 있습니다.

 

 

 

3. 정렬 기준 만들기

가끔 스트링의 문자열 중 2번째 자리로 정렬하거나, 이외의 특정 기준으로 정렬하고 싶을 때는 Comparator을 사용합니다.

    public static void main(String[] args) {
        PriorityQueue<String> priorityQueue = new PriorityQueue<>(new Comparator<String>() {
 
            @Override
            public int compare(String o1, String o2) {
                if(o1.charAt(1) < o2.charAt(1)) {
                    return -1;
                }else if(o1.charAt(1) > o2.charAt(1)) {
                    return 1;
                }else {
                    return 0;
                }
                
                /*
                return o1.compareTo(o2);            //전체 오름 차순
                return o2.compareTo(o1);            //전체 내림차순
                */
            }
        });
 
        priorityQueue.add("apple");
        priorityQueue.add("banana");
        priorityQueue.add("benq");
        priorityQueue.add("keyboard");
 
        
        while(!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());            //remove()를 사용하셔도 됩니다.
        }
    }
 

/*출력*/ 2번 째 자리에 있는 a e e p 순으로 정렬됨
banana
keyboard
benq
apple

new Comparator<자료형>() 에 익숙하지 않은 분들이 있습니다.

 

코드를 기준으로 String형으로 정렬을 하고 싶을 때 주석에 있는 o1.compareTo(o2) (오름차순)을 사용하시면 되고,

 

특별히 두번 째 자리로만 정렬하고 싶다면 위의 코드 같이 작성하시면 됩니다.(오름차순)

 

if ~else 부분이 이해가 잘 안 가시는 분들은 <, >을 기준으로 정렬하고 싶은 곳을 음수, 양수로 생각하시면 편합니다.

 

예를 들어 첫 줄처럼 o1.charAt(1) < o2.charAt(1) 일 경우 -1 이면 '<' 기준으로 왼쪽이니까.  작은 것을 기준으로 정렬하는구나~ 하시면 좋을 것 같습니다.

 

else if 에서는 '>' 기준 오른쪽이 작은 거니까 1. 같을 때는 0으로 정렬해주지 않습니다.