우선순위 큐(Priority Queue)

개요

---

• 우선순위 큐는 일반적인 큐의 구조를 가지지만 결정된 우선순위에 따라 데이터를 꺼낼 수 있다.
• 일반적으로 Heap을 이용하여 구현하며 이진트리 구조로 구성되어있다.
• 데이터를 삽입할 때 우선순위를 기준으로 최대 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸다.
• 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행된다.

 

우선순위 큐 사용법

---

Priority Queue 선언

import java.util.PriorityQueue;

//우선순위 : 낮은 숫자순
PriorityQueue<Integer> q1 = new PriorityQueue<>();
 
 //우선순위 : 높은 숫자순
 PriorityQueue<Integer> q2 = new PriorityQueue<>(Collections.reverseOrder());
 
q1.add(1);
q1.add(2);

//우선순위 가장 높은 값 참조 print:1
q1.peek();

 

 

Priority Queue 구현

class Solution implements Comparable<Solution>{
    private int rowNum;
    private String contents;

    public Solution(int rowNum, String contents){
        this.rowNum = rowNum;
        this.contents = contents;
    }
    public int getRowNum() {
        return this.rowNum;
    }

    public String getContents() {
        return this.contents;
    }
    @Override
    public int compareTo(Solution solution) {
        if (this.rowNum > solution.getRowNum())
            return 1;
        else if (this.rowNum < solution.getRowNum())
            return -1;
        return 0;
    }
    public static void main(String[] args) {

        PriorityQueue<Solution> priorityQueue = new PriorityQueue<>();

        priorityQueue.add(new Solution(3650, "10년 후"));
        priorityQueue.add(new Solution(31, "한달 후"));
        priorityQueue.add(new Solution(1, "첫해"));
        priorityQueue.add(new Solution(365, "1년 후"));

        while (!priorityQueue.isEmpty()) {
            Solution solution = priorityQueue.poll();
            System.out.println(solution.getRowNum() + " : " + solution.getContents());
        }
    }
//1 : 첫해
//31 : 한달 후
//365 : 1년 후
//3650 : 10년 후

 

 

정렬과 다른 점은?