Priority Queue

Queue에 우선순위 개념을 도입한 자료 구조로, 기존의 Queue가 먼저 들어온 것이 먼저 나가는 FIFO(First-in First-out) 형식인 것과 달리 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.

C++ priority queue

C++에서 priority queue는 queue 라이브러리에 들어있으며, 기본적으로 max heap으로 구현되어 있다. 쉽게 min heap으로 바꿀 수 있는 방법 중 한 가지는 push, top 연산 시 -를 붙이는 것이다!

주요 연산은 다음과 같은 것들이 있다.

push: priority queue에 원소를 추가
pop : priority queue에서 우선순위가 높은 원소를 제거
top: priority queue에서 우선순위가 높은 원소를 반환
empty: priority queue가 비어있는지 알려줌 (비어 있으면 True)
size: priority queue의 크기를 알려줌

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;  // pq라는 이름을 가진 priority queue 선언
 
    // priority queue에 원소를 삽입 (push) 한다 
    pq.push(8);
    pq.push(22);
    pq.push(1);
    pq.push(10);
    pq.push(7);
    
    if(pq.empty()) cout << "priority queue is empty!\n"; // priority queue가 비어 있는지 확인 하는 연산 
    else cout << "priority queue size is " << pq.size() << '\n'; // 비어 있지 않으므로 else문 실행
    
    while (!pq.empty()) { // 순서대로 꺼내보자! 22, 10, 8, 7, 1 순서로 출력될 것이다.
        cout << pq.top() << '\n';
        pq.pop();
    }
    
    if(	pq.empty()) cout << "priority queue is empty!\n"; // 이번에는 priority queue가 비어 있으므로 if문 실행
    else cout << "priority queue size is " << pq.size() << '\n';
    
    return 0;
}

priority queue 구현

priority queue를 구현할 수 있는 여러 방법이 있지만, 그 중에서도 가장 효율적인 방법은 바로 Heap을 이용하는 것이다. Heap을 이용하면 insert/delete 모두 O(log n) 시간 복잡도를 가지게 된다! 그렇다면 Heap이란 무엇일까? 아래 글을 참고하자 😋

Heap

priority queue의 일종으로 tree를 이용하여 구현한 priority queue라고 생각하면 될 것 같다! heap이 되기위해서는 relation property(node간의 관계)와 structural property(시간 복잡도를 O(log n)으로 유지하기 위한 balance) 두가지를 만족해야한다. heap은 크게 최대힙(max heap)과 최소힙(min heap) 두가지로 구분할 수 있다.

최대힙 (Max heap)

• relation property: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같음
  = 값이 큰 게 높은 우선순위를 가진다!
• structural property: 완전 이진 트리 (마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있음)

최소힙 (Min heap)

• relation property: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같음
  = 값이 작은 게 높은 우선순위를 가진다!
• structural property: 완전 이진 트리 (마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있음)

Heap 연산의 시간 복잡도

Insertion

structural property를 만족시키기 위해 tree의 마지막 위치 다음에 insertion한다. 이후 relation property를 맞춰 주기 위해 root에 도달하거나 heap의 relation property를 만족할 때 까지 올라가면서 parent의 값과 swap()을 진행해준다!
=> O(log n)

Deletion

structural property를 만족시키기 위해 last node를 값을 root로 올린 후 last node를 삭제한다.(last node와 root node를 가리키는 포인터 혹은 변수를 하나두면 O(1)에 가능하다!) 이후 relation property를 맞춰 주기 위해 leaf에 도달하거나 heap의 relation property를 만족할 때까지 child 중 더 작은(min heap의 경우) or 큰(max heap의 경우) 값과 swap()하면서(그렇지 않은면 또 swap()이 필요하다!!) 밑으로 내려가준다!
=> O(log n)

배열로 heap을 구현할 경우

• index 1부터 사용 (계산이 쉬워진다! 아래를 보면 알 수 있다!)
• left child = parent*2
• right child = parent*2 + 1
• parent = (left or right)child/2