[Java] 힙(Heap) - PriorityQueue

PriorityQueue 는 우선순위가 가장 높은것을 빼는 규칙입니다.

 

동작방식

1. 자료를 넣는다.
2. 자료 삭제시 가장 우선순위 높은걸 삭제,
3. 자료 읽을때 우선순위 가장 높은것을 읽는다.

시간복잡도

자료를 넣고 빼는 속도 모두 : logN

기본코드

PriorityQueue의 기본코드 입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;


public class PriorityQueue_example_0 {

	/**
	 * Priority Queue - Heap 으로 가장 많이 구현되어있다.
	 *  - 먼저넣은 것중 우선순위가 높은 것을 뺀다.
	 *  - 자료를 넣고 빼는 속도 모두 : logN
	 *  - max, min 값 찾기에 많이 쓰임
	 */
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	
    public static void main(String[] args) throws IOException {

        // min heap - 가장 위(0)가 가장 작은값 
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        
        q.add(5);
        q.add(3);
        q.add(7);
        q.add(4);
        q.add(5);
        
        System.out.println(q.poll());
        System.out.println(q.poll());
        System.out.println(q.poll());
        System.out.println(q.poll());
        System.out.println(q.poll());
        System.out.println(q.poll());
        
        System.out.println("=======================");
        // max heap - 가장 위(0)가 가장 큰값 
        PriorityQueue<Integer> qr = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        qr.add(5);
        qr.add(3);
        qr.add(7);
        qr.add(4);
        qr.add(5);
        
        // 빼지않고, 가장 우선순위 
        
        System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
        System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
        System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
        System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
        System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
        System.out.println(qr.poll()); // 가장 큰 하나를 제거하고 출력
        // --> 힙소트
        
		br.close();
		bw.close();

    }
}

결과는 다음과 같습니다.

3
4
5
5
7
null
=======================
7
5
5
4
3
null

 

아래는 class를 PriorityQueue에 넣어 우선순위를 조절해주어 실행해보는 코드입니다.

import java.io.IOException;
import java.util.PriorityQueue;

class Nodes implements Comparable<Nodes> {
    int a;
    int b;

    Nodes(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(Nodes tar) {
        if (tar.a > this.a) return 1;
        if (tar.a < this.a) return -1;
        
        if(tar.b > this.b) return 1;
        if(tar.b < this.b) return -1;
        return 0;

    }

}

public class PriorityQueue_example_1 {
    public static void main(String[] args) throws IOException {

        PriorityQueue<Nodes> q = new PriorityQueue<Nodes>();

        q.add(new Nodes(1, 2));
        q.add(new Nodes(5, 1));
        q.add(new Nodes(5, 3));
        q.add(new Nodes(1, 2));
        q.add(new Nodes(4, 6));

        System.out.println(q.peek().a + " " + q.peek().b);
        q.poll();
        System.out.println(q.peek().a + " " + q.peek().b);
        q.poll();
        System.out.println(q.peek().a + " " + q.peek().b);
        q.poll();
        System.out.println(q.peek().a + " " + q.peek().b);
        q.poll();
        System.out.println(q.peek().a + " " + q.peek().b);
        q.poll();
    }
}

결과는 아래와 같습니다.

5 3
5 1
4 6
1 2
1 2

compareTo 함수를 오버라이드하여 class 내부적으로 순서를 조절하여 우선순위를 만들어 첫번째 숫자가 큰순, 두번째 수가 큰순으로 우선순위를 부여하여 큐에서 빼낸 결과입니다.