개요

우선순위 큐란 자료구조의 한 종류이다.
큐(Queue)는 FIFO(First In,First Out)의 형태로
먼저 들어온 값이 먼저 나가는 형태지만,
우선순위 큐는 들어온 값의 우선순위를 비교해,
우선순위가 높은 순서대로 나가는 형태이다.

heap 자료구조와 유사해 heap을 이용해 만들었는데,
heap이란 완전 이진트리를 기본으로 한 자료구조로
두가지 형태가 있다.

부모 노드의 키값이 자식 노드보다 항상 큰 힙을
최대힙이라 부르고,
부모 노드의 키값이 자식 노드보다 항상 작은 힙을
최소힙이라 부른다.

이 중 최대힙을 이용해 우선순위가 높은 값이
앞으로 나오게 구현을 하였다.

코드

#include<iostream>
#include<vector>
using namespace std;

template <typename T >	

class priority_queue {							//max_heap기준
private:
	int p_size;
	vector<T> v;
public:
	priority_queue(){
		p_size = 0;
		v.push_back(0);							//우선순위큐는 루트노드를 1로잡는다.
	}
	void push(const T& elem) {
		v.push_back(elem);						//벡터에 값 푸시

		if (empty()) {							//루트에 이미 0넣었으므로 
			p_size++;
			return;
		}

		int idx = v.size() -1,parent=0,child=0;	//idx는 방금 들어온 값의 인덱스, 부모노드, 자식 노드
		while (idx > 1) {						//idx가 루트보다 위 일때
			child = idx;						//자식노드에 idx
			parent = idx / 2;					//부모 노드에 idx/2
			if (v[parent] < v[child]) {			//parent가 자식노드보다 작으면 바꾸기
				swap(v[parent], v[child]);
				idx = parent;					//idx에 parent값 넣어주고 while문 반복
			}
			else
				break;							//parent가 자식보다 크면 냅두기
		}
		p_size++;

	}
	void heapify(const int& idx) {					//pop후 제자리값 찾아가게 하기
		int curIdx = idx;
		int left = 2 * idx;
		int right = 2 * idx+1;

		if (left <= v.size() - 1 && v[curIdx] <= v[left]) {					//curIdx가 left보다 작으면 curidx=left
			curIdx = left;
		}
		if (right <= v.size() - 1 && v[curIdx]<= v[right] ) {					//curidx가 left보다 크면 curidx일거고, left보다 작으면 left값이다
												//이상태로 right와 비교하면 curidx와 left,right 다 비교된것.
			curIdx = right;
		}
		if (curIdx != idx) {					//curidx가 idx와 같지 않다면 변경 됬으므로
			swap(v[curIdx], v[idx]);
			heapify(curIdx);
		}

	}
	void pop() {
		if (empty()) {
			cout << "우선순위 큐 비어있음";
			return;
		}
		swap(v[1], v[v.size() - 1]);			//제일큰값 마지막값과 바꿔준후
		v.pop_back();							//마지막값 배출
		heapify(1);
		p_size--;
	}
	T top()
	{
		return v[1];
	}
	int size()
	{
		return p_size;
	}
	bool empty()
	{
		if (p_size) return false;
		else return true;
	}
	void print() {
		cout << "우선순위 큐의 원소들: ";
		for (int i = 1; i < v.size(); i++) {
			cout << v[i]<<" ";
		}
		cout << '\n';
	}
};

int main() {
	priority_queue<int> pq;

	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(4);
	pq.push(5);
	cout << pq.top()<<'\n';

	pq.print();

	pq.pop();
	cout << pq.top()<<'\n';
	pq.pop();
	cout << pq.top() << '\n';
	pq.pop();
	cout << pq.top() << '\n';

	pq.print();
}

• push(T elem) 함수에선
  elem 값을 priority_queue의 vector에 push_back 해준 뒤,
  부모노드와 비교하여 더 크면 부모노드랑 swap()을 반복하여
  자신의 위치를 찾아간다.

• pop() 함수에선
  제일 큰 값을 (최대힙이므로 v[1]에 위치)
  벡터의 맨뒤 값과 swap한 후,
  제일 큰 값을 pop해준다.

  그 후, v[1]에 들어온 값을 heapify() 함수를 통해
  제 위치로 보낸다.
  

• heapify(const int& n) 함수에선
  먼저 curIdx값에 n을 넣어준다.
  n번째 인덱스에서 자신의 자식 노드인 2n, 2n+1 값과
  각각 비교 후,
  만약 자식 노드값이 더 크다면 curIdx변수를 자식 노드로 이동시킨다.

  마지막에 curIdx가 n값과 변경되었다면
  자식노드보다 작은 부모노드가 있다는 뜻이므로
  v[n]값과 v[curIdx]값을 swap 해준다.
  이걸 반복하면 모든 원소가 최대힙을 만족하게 된다.

  문풀후생

  heap 자료구조를 이용해 풀면서
  부모노드와 자식노드간의 관계에 대해 알게 되었다.
  정렬의 시간복잡도가 O(nlogn)이고
  삽입과 삭제는 O(logn)인 효율적인 구조라
  익혀두면 좋을 것 같다.