우선순위큐(Priority Queue) [자료구조] ( 프로그래머스 LV2 .더맵게)

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

자 이제 Queue는 아는데 위 문제와 같이 일정 기준으로 정렬을 계속해서 해줘야 하는 경우(우선순위가 존재하는 경우) Priority Queue를 써주면 더 편리하게 코드를 짤 수 있다.

 

우선순위 큐(Priority Queue)

Queue는 부가적인 기능 없이 오직 먼저 들어온 데이터가 먼저 나가는 First In First Out (FIFO) 구조로 되어있다.

하지만 우선순위 큐는 들어간 순서에 상관없이 우선순위대로 데이터가 나온다.

 

우선순위 큐를 배열이나 연결리스트로 구현하지 않는 이유

https://suyeon96.tistory.com/31

배열로 구현하는 경우

우선순위가 높은 순서대로 넣으면 삭제는 맨앞에서 하면 되니까 시간이 많이걸리지는 않는다.

하지만 삽입을 할때에는 인덱스를 모두 한칸씩 뒤로 밀어야하니 효율적이지 않다.

삭제 O(1) 

삽입 O(N)

 

연결리스트로 구현하는 경우

이 또한 우선순위가 높은 순서대로 넣으면 삭제는 얼마 걸리지 않지만 삽입이 그 위치를 찾기까지 시간이 많이 걸린다.

삭제 O(1)

삽입 O(N)

 

우선순위 큐를 힙(Heap)으로 구현하는 이유

삭제 삽입 O(logN)

힙이란?

힙은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다.

여러개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠른다.

힙의 경우 삭제와 삽입의 과정에서 모두 부모와 자식 간의 비교만 계속 진행된다.

 

힙의 특징

완전이진트리 형태로 이루어져있다.

부모노드와 서브트리간 대소 관계가 성립된다. ( 반정렬 상태 )

이진탐색트리(BST)와 달리 중복 값이 허용된다.

 

힙의 종류

https://chunsubyeong.tistory.com/88

 

최대 힙

부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다.

 

최소 힙

부모 노드의 키 값이 자식 노드보다 작거나 같은 완전 이진트리이다.

 

 

우선순위 큐 구현

힙은 일반적으로 배열을 이용하여 구현한다.

완전이진트리이므로 중간에 비어있는 요소가 없기 때문이다.

 

 

삽입연산

힙에 삽입을 하기 위해서는 힙 트리의 성질을 만족시키면서 새로운 요소를 추가해야한다.

 

우선 완전이진트리의 마지막 노드에 이어서 새로운 노드를 추가한다.

추가된 새로운 노드를 부모의 노드와 비교하여 교환한다.

정상적인 힙트리가 될 때까지 (더이상 부모와 교환할 필요가 없을 때까지) 반복

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

삭제연산

힙 트리에서 루트노드가 가장 우선순위가 높으므로 루트 노드를 삭제해야한다.

삭제가 이뤄진 후 힙 트리의 성질이 유지되어야 한다.

 

루트를 삭제하고 삭제된 빈자리에 완전이진트리의 마지막 노드를 가져온다.

루트 자리에 위치한 새로운 노드를 자식 노드와 비교하여 교환한다.

정상적인 힙트리가 될때까지 반복

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

 

우선순위 큐 (Priority Queue) 선언

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();
//높은 숫자가 우선 순위인 int형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder);

 

 

다시 <더 맵게>를 풀어보자.

import java.util.PriorityQueue;
import java.util.Arrays;

class Solution {
    public PriorityQueue<Integer> queue = new PriorityQueue<>();
    int K;
    public int solution(int[] scoville, int K) {
        int answer = 0;

        this.K = K;
        Arrays.sort(scoville);
        
        for(int x : scoville){
            queue.offer(x);
        }
        
        while(!isMoreHot()){
            if(queue.size()==1) return -1;
            mixHot();
            answer++;
        }
        return answer;
    }
    public void mixHot(){
        int min_first = queue.poll();
        int min_second = queue.poll();
        queue.offer(min_first+min_second*2);
    }
    public boolean isMoreHot(){
        for(int x : queue){
            if(x<K) return false;
        }
        return true;
    }
}

 

 

큐에 이어서 우선순위 큐까지 배워봤다.

우선순위 큐를 통해 더 알고리즘을 푸는데에 다양한 사고를 할 수 있게되어서 좋다.