우선순위 큐를 이용한 힙 구현

Queue : Fist-in-First-Out
Heap : 중복값이 허용되며 최소힙과 최대힙이 있는 완전이진 트리

힙은 우선순위큐를 이용해서 구현될 수 있다.

최소힙 (백준의 1927번)

• 처음에 다소 복잡한 방식으로 접근하였다. 하지만 정답

import java.util.*;
import java.io.*;

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        Map<Long,Integer> map = new TreeMap<>();

        for(int i=0;i<N;i++){
            long x = Integer.parseInt(br.readLine());
            if(x>0){
                map.put(x,map.getOrDefault(x,0)+1);
            }else {
                if(map.size()==0) {
                    bw.write("0\n");
                    continue;
                }
                Set<Long> keyset = map.keySet();
                Iterator it = keyset.iterator();
                long remv = (Long) it.next();
                map.put(remv, map.get(remv)-1);
                if(map.get(remv)==0) map.remove(remv);
                bw.write(Long.toString(remv)+"\n");



            }

        }
        bw.flush();
        bw.close();
        br.close();


    }


}

• 우선순위 큐를 이용한 방법

import java.util.*;
import java.io.*;

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Long> heap = new PriorityQueue<>();
        for(int i=0;i<N;i++){
            long x = Integer.parseInt(br.readLine());
            if(x>0){
                heap.offer(x);
            }else {
                if(heap.isEmpty()){
                    bw.write("0\n");
                }else{
                    bw.write(Long.toString(heap.poll())+"\n");
                }

            }

        }
        bw.flush();
        bw.close();
        br.close();


    }


}

최대힙

import java.util.*;
import java.io.*;

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> heap = new PriorityQueue<>((x1,x2)-> x2-x1);
        for(int i=0;i<N;i++){
            int x = Integer.parseInt(br.readLine());
            if(x>0){
                heap.offer(x);
            }else {
                if(heap.isEmpty()){
                    bw.write("0\n");
                }else{
                    bw.write(Long.toString(heap.poll())+"\n");
                }

            }

        }
        bw.flush();
        bw.close();
        br.close();


    }


}

위와 같은 방법으로 해도 되긴하지만 추천하진 않는거 같다.