[DS] Priority Queue란?

Priority라는 단어의 뜻은 아래와 같다.

 

우선 사항 / 우선, 우선권

 

이 단어에 자료구조 중 하나인 Queue(큐)가 붙었다. Queue는 무엇인가?

큐는 먼저 넣은 데이터가 먼저 나오는 First In First Out 구조로 데이터가 저장되는 자료구조다.

먼저 넣은 게 먼저 나오는데, 우선순위를 붙여야 하는 이유가 있을까? 넣은 순서대로 빼는 것보다 다른 요소를 먼저 빼는 게 필요해서 Priority Queue가 만들어진 건가?

위키백과에서 말하는 Priority Queue는 아래와 같다.

 

https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90

우선순위 큐 - 위키백과, 우리 모두의 백과사전

우선순위 큐는 평범한 큐, 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서 높은 우선순위를 가진 원소는 낮은 우선순위의 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위라면 큐에서 그들의 순서에 의해 처리된다
우선순위 큐가 힙이라는 건 널리 알려진 오류다. 우선순위 큐는 리스트, 맵 같이 추상적인 개념이다. 리스트는 연결 리스트나 배열로 구현될 수 있는 것처럼 우선순위 큐는 힙이나 다양한 다른 방법으로 구현될 수 있다. 우선순위 큐는 최소한 다음 연산이 지원돼야 한다.

- insert_with_priority : 하나의 원소를 우선순위를 지정해 큐에 추가한다
- pull_highest_priority_element : 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환한다

 

https://en.wikipedia.org/wiki/Priority_queue

Priority queue - Wikipedia

우선순위 큐는 각 요소에 추가로 연결된 우선순위가 있는 일반 대기열 또는 스택 자료구조와 유사한 추상 데이터 유형이다. 우선순위 큐에서 우선순위가 높은 요소는 낮은 요소보다 먼저 제공된다. 일부 구현에서 두 요소의 우선순위가 같으면 큐에 넣은 순서에 따라 제공되지만 다른 구현에선 우선순위가 같은 요소의 순서가 정의되지 않는다. 우선순위 대기열은 종종 힙으로 구현되지만 개념적으론 힙과 다르다. 우선순위 큐는 리스트 또는 맵과 같은 개념이다. 리스트가 링크드 리스트나 배열로 구현될 수 있는 것처럼 우선순위 큐는 힙이나 정렬되지 않은 배열 같은 다른 방법으로 구현될 수 있다. 우선순위 큐는 최소한 다음 연산이 지원돼야 한다.

- is_empty : 큐가 비어있는지 확인한다
- insert_with_priority : 연결된 우선순위를 써서 요소를 큐에 추가한다
- pull_highest_priority_element : 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환한다. pop_element(Off), get_maximum_element, get_front(most)_element라고도 한다

또한 가장 높은 우선순위 요소를 반환하지만 대기열을 수정하지 않는 peek은 매우 자주 구현되며 거의 항상 O(1) 시간에 실행된다. 고급 구현은 pull_lowest_priority_element, 처음 몇 개의 가장 높은 우선순위 또는 가장 낮은 우선순위 요소 검사, 대기열 지우기, 대기열의 하위 집합 지우기, 일괄 삽입 수행, 둘 이상의 큐를 하나로 병합, 우선순위 증가와 같은 복잡한 작업을 지원할 수 있다. 모든 요소 등 스택과 큐는 우선순위 큐와 다르다

 

다른 사람들은 어떻게 설명하는지 확인해봤다.

 

https://hannom.tistory.com/36

[자료구조] 우선순위 큐(Priority Queue) - 1

큐는 연산 결과로 먼저 들어간 데이터가 먼저 나오나, 우선순위 큐는 다르다. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 병원 응급실을 예로 들면 제일 응급한 환자부터 치료를 하게 된다. 즉 우선순위가 높은 환자가 먼저 치료를 받는 것이다. 이렇게 우선순위 큐에서 중요한 것은 우선순위다. 데이터를 근거로 우선순위를 판단해야 하고, 우선순위를 프로그래머가 판단해서 결정해야 한다. 우선순위 큐를 구현하는 방법은 3개다.
1. 배열 기반 구현
2. 링크드 리스트 기반 구현
3. 힙(Heap)을 이용한 구현...(중략)

 

https://yoongrammer.tistory.com/81?category=987044 

[자료구조] 우선순위 큐 (Priority Queue) 개념 및 구현

우선순위 큐는 다음과 같은 속성을 갖고 있다.
1. 모든 항목엔 우선순위가 있다
2. 우선순위가 높은 요소는 낮은 요소보다 먼저 큐에서 제외된다
3. 두 요소의 우선순위가 같으면 큐의 순서에 따라 제공된다

4 -> 8 -> 2 순으로 데이터가 들어갔을 때 큐와 우선순위 큐의 처리 순서는 아래와 같다. 높은 값이 우선순위를 갖는다고 가정한다.
큐 : 4 -> 8 -> 2
우선순위 큐 : 8 -> 4 -> 2

 

아래는 Priority Queue의 예시 코드들이다. 숫자를 오름차순, 내림차순으로 큐에서 빼내 출력하는 예시다.

public class PriorityQueueImpl {

    public static int[] arr = {9, 1, 8, 3, 5, 6, 7, 4, 2};

    public static void main(String[] args) {
        Heap heap = new Heap();

        for (int i = 0; i < arr.length; i++)
            heap.push(arr[i]);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(heap.pop() + " "); // 1 2 3 4 5 6 7 8 9
        }
    }

    public static class Heap {
        int[] heap = new int[100];
        int count = 0;

        public Heap() {}

        public void push(int x) {
            heap[++count] = x;
            int index = count;
            while (index > 1 && heap[index / 2] > heap[index]) {
                if (index == 1 || heap[index / 2] < heap[index])
                    break;
                int tmp = heap[index / 2];
                heap[index / 2] = heap[index];
                heap[index] = tmp;
                index /= 2;
            }
        }

        public int pop() {
            int pop = heap[1];
            heap[1] = heap[count--];
            int index = 1;
            int next;
            while (true) {
                next = index * 2;
                if (next < count && heap[next] > heap[next + 1])
                    next++;
                if (next > count || heap[next] > heap[index])
                    break;
                int tmp = heap[index];
                heap[index] = heap[next];
                heap[next] = tmp;
                index = next;
            }
            return pop;
        }
    }
}

public class PriorityQueueImpl {

    public static int[] arr = {9, 1, 8, 3, 5, 6, 7, 4, 2};

    public static void main(String[] args) {
        Heap heap = new Heap();

        for (int i = 0; i < arr.length; i++)
            heap.push(arr[i]);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(heap.pop() + " "); // 9 8 7 6 5 4 3 2 1
        }
    }

    public static class Heap {
        int[] heap = new int[100];
        int count = 0;

        public Heap() {
        }

        public void push(int x) {
            heap[++count] = x;
            int index = count;
            while (index > 1 && heap[index / 2] < heap[index]) {
                if (index == 1 || heap[index / 2] > heap[index])
                    break;
                int tmp = heap[index / 2];
                heap[index / 2] = heap[index];
                heap[index] = tmp;
                index /= 2;
            }
        }

        public int pop() {
            int pop = heap[1];
            heap[1] = heap[count--];
            int index = 1;
            int next;
            while (true) {
                next = index * 2;
                if (next < count && heap[next] < heap[next + 1])
                    next++;
                if (next > count || heap[next] < heap[index])
                    break;
                int tmp = heap[index];
                heap[index] = heap[next];
                heap[next] = tmp;
                index = next;
            }
            return pop;
        }
    }
}

 

 

참고한 사이트)

 

https://yunmap.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Java%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%89%AC%EC%9A%B4-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-Priority-Queue

[알고리즘] Java로 구현하는 쉬운 우선순위 큐 (Priority Queue)