Priority Queue

개요

Entry를 담는 ADT로, Entry는 보통 key를 우선순위로 하는 { key, value } 쌍이다.

 

우선순위에 따라 정렬되는 Queue로, Entry 간 Total order relation이 성립한다.

 

 

Priority Queue

대표적인 operation은 insert, removeMin이 있고, 추가로 min, size, empty 등을 지원할 수 있다.

 

List-based 구현으로 sorted list를 이용하는 방법과 unsorted list를 이용하는 방법이 있다.

 

 

Total order relation

전순서라고 하며,

 

• Reflexive property ( x ≤ x )
• Antisymmetric property ( x ≤ y and y ≤ x then x = y )
• Transitive property ( x ≤ y and y ≤ z then x ≤ z )

 

위 세 property가 성립한다.

 

 

Comparator ADT

isLess(p, q), 즉 bool(p < q)를 구현하는 ADT.

 

C++로는 ()를 overload 하여 다음과 같이 구현할 수 있다.

 

class comp {
    bool operator() (const T& p, const T& q) const {
        return p.key < q.key;
    }
}

 

Sorted list 기반 구현

Insertion sort로 할 수 있다.

 

원소 하나 삽입에 O(n), 삭제에 O(1) 이다.

 

 

Unsorted list 기반 구현

Selection sort로 할 수 있다.

 

원소 하나 삽입에 O(1), 삭제에 O(n) 이다.

 

 

In-place Insertion sort

입력으로 주어진 sequence에 대해, 1, 2, ..., n번 인덱스에서 출발해서 앞에 더 이상 자신보다 큰 원소가 없을 때까지 swap 한다.

 

정렬을 마치는데 O(n^2) 이다.

 

 

Implementation

아래는 이론에서 배운 내용을 구현한 코드이다.

 

Doubly linked list를 이용한 Sorted list 기반 우선순위 큐이다.

 

Heap 기반 우선순위 큐가 훨씬 좋아 별로 중요하지 않다.

 

#include <bits/stdc++.h>
using namespace std;

struct pii {
	int k, v;
	pii() { k = v = -1; }
	pii(int key, int value) { k = key, v = value; }
};

struct Node {
	pii dat;
	Node* prev, * next;
	Node(int key, int value) {
		dat = pii(key, value);
		prev = next = nullptr;
	}
	void print() { cout << "{ " << dat.k << ", " << dat.v << " } - "; if (next) next->print(); }
};

struct PQ {
	int sz;
	Node* root;

	PQ() {
		sz = 0;
		root = nullptr;
	}
	void insert(int key, int value) { // insertion
		Node* newNode = new Node(key, value);
		if (empty()) {
			root = newNode;
		}
		else {
			Node* cur = root;
			while (cur) {
				if (newNode->dat.k < cur->dat.k) {
					if (cur == root) {
						root = newNode;
						newNode->next = cur;
						cur->prev = newNode;
						break;
					}
					else {
						cur->prev->next = newNode;
						newNode->prev = cur->prev;
						newNode->next = cur;
						cur->prev = newNode;
						break;
					}
				}
				if (!cur->next) {
					cur->next = newNode;
					newNode->prev = cur;
					break;
				}
				cur = cur->next;
			}
		}
		sz++;
	}
	int removeMin() {
		if (empty()) return -1;
		sz--;
		int ret = root->dat.v;
		if (!root->next) {
			delete root;
			root = nullptr;
		}
		else {
			Node* temp = root;
			root = root->next;
			root->prev = nullptr;
			delete temp;
		}
		return ret;
	}
	int min() { return (empty() ? -1 : root->dat.v); }
	int size() { return sz; }
	bool empty() { return (sz == 0); }
	void print() { if (!empty()) root->print(); cout << "\n"; }
};

int main() {
	PQ pque;
	int TEST; cin >> TEST; while (TEST--) {
		string oper; int p, q; cin >> oper;
		if (oper == "insert") { cin >> p >> q; pque.insert(p, q); }
		if (oper == "remove") cout << pque.removeMin() << "\n";
		if (oper == "min") cout << pque.min() << "\n";
		if (oper == "size") cout << pque.size() << "\n";
		if (oper == "empty") cout << (pque.empty() ? "YES" : "NO") << "\n";
		if (oper == "print") pque.print();
	}
}