Priority queue

evelyn82ny·2022년 1월 21일
0

Algorithm

목록 보기
9/9

Queue 는 FIFO (first in first out) 로 들어온 순서대로 정렬된다. 이와 달리 Priority Queue 는 우선 순위가 높은 순서대로 정렬된다. root 노드의 우선 순위가 제일 높기 때문에 설정한 우선 순위에 따라 원하는 값을 O(1) 시간복잡도로 찾을 수 있다는 것이 장점이다.

Full binary tree VS Complete binary tree

Full binary tree 는 모든 level 의 노드가 다 채워져 있는 구조이다.

Complete binary tree 는 leaf 가 있는 마지막 level 은 모두 채워져 있지 않아도 된다. 하지만 마지막 level 을 제외한 모든 level 은 채워져 있어야 한다. 새로운 노드를 추가할 땐 왼쪽부터 채워나간다.

Heap 은 Complete binary tree 을 기본으로 한 자료구조이다. Priority queue 는 heap 을 응용한 자료구조이다.

Complete binary tree VS Binary search tree

Heap (complete binary tree) 은 우선순위가 높은 순으로 정렬된다. 즉, 부모 노드로 갈수록 우선순위가 높다. 같은 level 의 노드 끼리는 비교할 필요가 없고, 부모와 자식 노드간의 비교로만 정렬이 이루어진다.

Binary search tree (BST) 는 부모와 왼쪽 자식 노드, 부모와 오른쪽 자식 노드간의 비교가 필요하다. 오른쪽 그림인 BST 를 보면 부모 노드를 기준으로 왼쪽 자식 노드는 부모 값보다 작고, 오른쪽 자식 노드는 부모 값보다 크다는 것을 알 수 있다.

또한, Heap 은 Complete binary search 로 왼쪽부터 채워나가야 하지만 BST 는 왼쪽부터 채울 필요가 없다. 이로 인해 BST 는 최악의 경우 skewed 구조가 되기도 한다. Binary search 를 사용하려는 이유는 O(logN) 시간복잡도를 갖기 때문이다. skewed 구조가 될 경우 O(N) 시간복잡도를 갖기 때문에 tree 를 사용하는 의미가 없어진다. 이를 해결하기 위해 Balanced binary search tree 으로 시간복잡도 O(logN) 이 되도록 유지하며 대표적인 예로 Red-black tree 와 Treap 이 있다.

min heap VS max heap

  • min heap : 부모 노드의 값 <= 자식 노드의 값 ( 작은 값이 우선순위가 높은 경우 )
  • max heap : 자식 노드의 값 <= 부모 노드의 값 ( 큰 값이 우선순위가 높은 경우 )

cpp 는 max heap 이 기본 설정이고, java 는 min heap 이 기본 설정이다. 언어마다 default 가 다름을 주의해야 한다.

push (java: add)

새로 들어온 19 는 현재 max-heap 에서 가장 우선 순위가 높기 때문에 root 에 위치해야 한다.

push 한 새로운 값은 현재 heap 의 마지막 노드에 추가된다. 그 후 부모 노드와 우선 순위를 비교하며 위치를 계속해서 바꿔나가는 과정을 거친다. 새로 들어온 19 는 마지막 노드인 index 6 에 위치한다.

트리 구조상 부모가 index 1 이면 부모 index X 2 인 index 2 가 왼쪽 자식 노드가 되고, 부모 index X 2 + 1 인 index 3 가 오른쪽 자식 노드이다. 반대로 왼쪽, 오른쪽 상관없이 자식 노드 / 2 값이 부모 노드가 된다.

이 원리를 이용해 index 6 에 위치한 새로운 값을 비교해 나가면 된다. index 6의 부모인 index 3 의 값은 5 이다. max-heap 에서 5 보다 19 의 우선순위가 높기 때문에 서로의 위치를 바꿔준다.

index 3 으로 올라온 19 는 index 3 의 부모인 index 1 과 비교한다. index 1 의 값인 17 보다 19의 우선순위가 더 높기 때문에 현재 올바른 순서가 아니다. 즉, 서로의 위치를 변경한다.

부모와의 우선순위가 올바르다면 더 이상의 탐색을 멈춘다. 하지만 이를 직접 개발할 일은 거의 없다. cpp 가 제공해주는 STL 을 가져다 쓰기만 하면 된다.

Tree 구조의 부모-자식 관계로 설명하지만 구현되는 방식은 배열이다.

  • 왼쪽 자식의 index = 부모의 index X 2
  • 오른쪽 자식의 index = 부모의 index X 2 + 1
  • 부모의 index = 자식의 index / 2

위 연산처럼 간단한 연산으로 특정 index 에 바로 접근할 수 있기 때문에 배열로 구현한다.

pop (java: poll)

우선순위가 제일 높은 root 노드의 값을 제거하기 위해 root 노드를 삭제한다면 왼쪽 sub tree 와 오른쪽 sub tree 로 분리된다. 이를 막기 위해 root 노드를 삭제하지 않고, 마지막 노드의 값을 root 노드에 복사하는 방식을 사용한다.

마지막 노드 값인 11 을 root 노드에 저장한다. 그다음 자식 노드와의 우선순위가 올바른지 확인해야 한다.

왼쪽 자식 노드와 오른쪽 자식 노드 중 우선순위가 더 높은 노드가 비교 대상이 된다. max heap 은 자식 노드 중 큰 값을 갖는 자식 노드와 비교를 하며, min heap 은 작은 값을 갖는 자식 노드와 비교한다.

해당 tree 는 max heap 이므로 12 를 갖는 자식 노드와 비교한다. 부모 노드의 값인 11 보다 자식 노드의 값인 12 의 우선순위가 높기 때문에 서로의 위치를 바꿔준다. 부모 자식간의 우선순위가 올바를 때까지 진행하면 된다.

cpp: Operator overloading

cpp 에서 Heap 의 기본 설정은 max heap 으로 자식보다 부모 노드의 값이 더 크다. max heap 이 기본 설정인 priority_queue 를 min heap 으로 사용하려면 다음과 같이 작성한다.

priority_queue<int, vector<int>, greater<int>> pq;

위와 같이 작성하지 않고 max heap 에 push 할 값 X -1 의 값을 push 하면 min heap 처럼 사용할 수 있다. 이 방식으로 값을 꺼내서 사용할 때는 -1 을 곱해 원래 값으로 되돌려야 한다.

아래와 같이 구조체로 priority queue 를 사용한다면 어떤 field 로 우선 순위를 정할 것인지 설정해야한다. 우선 순위를 작성하지 않을 경우 런타임 에러가 발생한다.

struct Node {
    int height;
    int cost;
    
    Node(int _height, int _cost) : height(_height), cost(_cost){}
    
    bool operator < (const Node &rhs) const {
    	return cost < rhs.cost;
    };
};

Node( -1, 5);
Node( 4, -9);
Node( 2, 3);
Node( 6, 11);

위 구조체를 사용한 vector 를 정렬한 결과는 다음과 같다.

Node( 4, -9), Node( 2, 3), Node( -1, 5), Node( 6, 11)

cost 가 작은 순서대로 정렬되었다. vector 에서는 < 작성 시 오름차순으로, > 작성 시 내림차순으로 정렬된다.

하지만 priority queue 의 정렬 결과는 정반대이다.

Node( 6, 11), Node( -1, 5), Node( 2, 3), Node( 4, -9)

cost 가 큰 순서대로 정렬되었는데 원래 있던 수새로 push 된 수를 비교하기 때문이다.

Node( -1, 5) 값이 있던 상태에서 Node( 4, -9) 를 push 했다. struct Node 의 정렬 기준은 cost < rhs.cost 이기 때문에 cost 만 비교하면 된다. 기존에 있던 부모 노드의 cost 5 > 새로운 자식 노드의 cost -9 를 통해 설정한 연산자 오버로딩을 만족하지 못한다. 즉, 기존에 있던 부모 노드의 우선순위가 더 높다는 의미이므로 서로의 자리를 바꾸지 않고 연산을 종료한다.

새로운 Node( 2, 3) 값을 push 했을 때도 마찬가지로 부모 노드의 cost 5 > 새로운 자식 노드의 cost 3 를 통해 설정한 연산자 오버로딩을 만족하지 못해 연산을 종료한다.

새로운 Node( 6, 11) 값을 추가했다. 부모 노드의 cost -9 < 새로운 자식 노드의 cost 11 를 통해 설정한 연산자 오버로딩을 만족하는 것을 알 수 있다. 이는 기존보다 비교 대상의 우선순위가 높기 때문에 서로의 위치를 변경해야 한다는 의미이다. 설정한 연산자 오버로딩을 만족할 때 까지 위치를 변경하면 된다.

java: Override

cpp 와 다르게 java 는 min heap 이 기본 설정이다. 만약 max heap 으로 사용하고 싶다면 아래와 같이 작성한다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

class 객체를 사용한다면 비교 기준을 정해야 한다. 작성하지 않을 경우 java: Node is not abstract and does not override abstract method compareTo(Node) in java.lang.Comparable 라는 에러가 발생한다.

public class Node implements Comparable<Node> {
    int height;
    int cost;

    @Override
    public int compareTo(Node rhs) {
        return this.cost - rhs.cost;
    }
}

pq.add(new Node(-1, 5));
pq.add(new Node(4, -9));
pq.add(new Node(2, 3));
pq.add(new Node(6, 11));

Priority queue 와 vector 둘다 cost 를 기준으로 오름차순으로 정렬된다.

Node( 4, -9), Node( 2, 3), Node( -1, 5), Node( 6, 11)

만약 내림차순으로 정렬하고 싶다면 아래와 같이 작성한다.

public class Node implements Comparable<Node> {
    int height;
    int cost;

    @Override
    public int compareTo(Node rhs) {
        return rhs.cost - this.cost;
    }
}

boj 1202: 보석 도둑

문제 링크: https://www.acmicpc.net/problem/1202
정답 코드: https://github.com/evelyn82ny/Algorithm/blob/master/Data_structure/_ps/boj_1202.cpp

보석에 대한 무게와 가격이 주어진다. 가방이 담을 수 있는 최대 무게도 정해져있다. 이때 여러 가방에 가져올 수 있는 보석의 최대 가격을 구하는 문제이다.

가져올 수 있는 보석의 최대 가격을 구해야 하지만, 보석의 가격에만 중점을 두면 시간초과가 발생할 수 있다. 아래 3개의 보석 중 가장 높은 가격은 114 이며 무게는 2 이다. 그러면 주어진 가방 중 해당 무게를 담을 수 있고, 다른 보석을 아직 담지 않은 가방을 찾아야 한다.

보석(N) 과 가방(K) 는 최대 3e5 개씩 주어진다. 위 방식으로 구현하면 O(NK) 의 시간복잡도로 9e10 이 되어 시간초과가 발생한다. 즉, 위 방식으로 해결할 수 없다.

담을 수 있는 최대 무게가 2 인 가방은 보석의 무게가 5인 보석을 제외한 나머지 보석 중 가격이 제일 높은 것을 선택하면 된다. 담을 수 있는 최대 무게가 10 인 가방은 모든 보석 중 가격이 제일 높은 것을 선택하면 된다. 즉, 가방의 무게가 클수록 선택할 수 있는 경우의 수가 많아지기 때문에 가방의 무게가 작은 것부터 처리해야 한다.

보석과 가방 둘다 무게를 기준으로 오름차순 정렬한다. 그 후 현재 가방 무게에 들어갈 수 있는 보석을 priority queue 에 담는다. 이때 priority queue 의 정렬 조건은 높은 가격이 우선순위가 높도록 설정하면 된다.

struct Jewelry{
    int weight, price;

    Jewelry(){}
    Jewelry(int _weight, int _price) : weight(_weight), price(_price) {}

    bool operator < (const Jewelry &rhs) const {
        return price < rhs.price;
    }
};

while(++bagIndex < bagWeight.size()) {

    // 현재 가방 무게에 들어갈 수 있는 보석 push
    while(jewelryIndex < jewels.size() && jewels[jewelryIndex].weight <= bagWeight[bagIndex])
        pq.push(jewels[jewelryIndex++]);

    if(!pq.empty()) {
        totalPrice += (long long)pq.top().price;
        pq.pop(); // 중복 사용을 막음
    }
}

현재 priority queue 에 담긴 보석은 현재 가방에 들어갈 수 있는 후보군이다. 높은 가격이 우선순위가 높도록 설정했기 때문에 root 에 있는 값이 현재 가방에 들어갈 수 있는 보석 중 가장 가격이 높은 보석이다.

가방의 무게도 오름차순으로 정렬했기 때문에 priority queue 에 남은 보석도 새로 탐색할 가방에 들어갈 수 있는 후보군이 되며 같은 방식으로 탐색하여 보석을 찾아내면 된다.

profile
🌈 즐겨보자고 🙌🏻

0개의 댓글