자바로 힙 사용하는 방법 - 백준 1927,11279 ( 최소힙, 최대힙)

 

안녕하세요 besforyou 입니다.

 

이번 글은 자바로 heap 자료구조를 사용하는 방법에 대해 소개하겠습니다.

 

---

PriorityQueue를 사용하면 됩니다.

 

1.  최소 힙

 

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

 

2.  최대 힙

 

최대힙에는 Comparator를 넣어줍니다.

 

 

람다 식

 

PriorityQueue<Integer> minHeap = new PriorityQueue<>
        ((Integer o1, Integer o2) -> ( -Integer.compare(o1,o2)));

 

 

오버라이드 버전

 

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

 

 

- 메소드 

 

힙에 새로운 원소 추가 :     add(E e)

root 원소 읽기 :         peek()

root 원소 읽고 제거 :     poll()

특정 원소 제거 :          remove(Object o)

 

기능	이름
힙에 새로운 원소 추가	add(E e)
root 원소 읽기	peek()
root 원소 읽고 제거	poll()
특정 원소 제거	remove(Object o)

 

 

백준 - 1927 최소힙 문제

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

import java.io.*; import java.util.*;   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;         N = Integer.parseInt(br.readLine());           PriorityQueue<Integer> minHeap = new PriorityQueue<>();           for (int i = 0 ; i < N ; i++) {             int x = Integer.parseInt(br.readLine());             if (x == 0) {                 if (minHeap.size() == 0) {                     bw.write(0 + "\n");                 } else {                     int min = minHeap.poll();                     bw.write(min + "\n");                 }             } else {                 minHeap.add(x);             }         }         bw.flush();         bw.close();     } }       Colored by Color Scripter

cs

 

백준 - 11279 최대 힙 문제

 

import java.io.*;
import java.util.*;
 
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;
        N = Integer.parseInt(br.readLine());
 
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>
                (new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return -Integer.compare(o1,o2);
                    }
                });
 
        for (int i = 0 ; i < N ; i++) {
            int x = Integer.parseInt(br.readLine());
            if (x == 0) {
                if (maxHeap.size() == 0) {
                    bw.write(0 + "\n");
                } else {
                    int min = maxHeap.poll();
                    bw.write(min + "\n");
                }
            } else {
                maxHeap.add(x);
            }
        }
        bw.flush();
        bw.close();
    }
}