우선순위 큐 : priority_queue (최대힙, 최소힙)

우선순위 큐(Priority Queue)

• 일반적인 큐는 제일 먼저 들어간 데이터가 가장 먼저 나오게 되는 자료구조이다.
• 이와 달리 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고, 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다.

 

최대힙

PriorityQueue의 생성자에 Collections.reverseOrder() 을 주어야 한다.

import java.util.*;

// 최대힙 (priority_queue : 우선순위 큐)
public class cp73 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        PriorityQueue<Integer> queue = 
        			new PriorityQueue<>(Collections.reverseOrder());

        while(true){

            int a = sc.nextInt();
            if(a == -1) break;
            if(a == 0){
                if(queue.isEmpty()){
                    System.out.println("-1\n");
                }else{
                    System.out.println("top = " + queue.poll());
                }
            }
            else{
                queue.add(a);
            }
        }
        //return 0;
    }
}

 

최소힙

최대힙과 동일하며 단지 PriorityQueue 생성자에 아무것도 주지 않으면 최소힙이 된다.

// 최소 힙 (priority_queue : 우선순위 큐)
public class cp74 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        while(true){
            int a = sc.nextInt();
            if(a == -1) break;
            if(a == 0){
                if(queue.isEmpty()){
                    System.out.println("-1\n");
                }else{
                    System.out.println("top = " + queue.poll());
                }
            }
            else{
                queue.add(a);
            }
        }// end while
    }
}