3-3. 우선순위 큐 구현 연습

0. std::priority_queue ; 우선순위 큐

int main()
{
	priority_queue<int> pq;

	pq.push(100);
	pq.push(300);
	pq.push(200);
	pq.push(500);
	pq.push(400);

	while (pq.empty() == false)
	{
		int value = pq.top();
		pq.pop();

		cout << value << endl;
	}

	return 0;
}

 

우선순위 큐는 std 안에서 구현되어 있다.

우선순위 큐는 힙 구조로 되어있기 때문에, 500 - 400 - 300 - 200 - 100 의 순서로 출력된다.

 

(1) 작은 값 순서대로 출력하기(오름차순)

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

 

1. 우선순위 큐 구현

 

(1) 기본 구조

std::priority_queue를 본따서 만든 클래스인 PriorityQueue를 구현하는 것을 목표로 한다.

우선순위 큐를 구현하기 위해 다양한 컨테이너를 활용할 수 있으므로, 템플릿에서 여러 컨테이너를 쓸 수 있게 한다.

다만 여기에서는 벡터로 구현한다.

template<typename  T, typename Container = vector<T>> // 기본값은 벡터
class PriorityQueue
{
public:

	bool empty()
	{
    
	}

	T& top()
	{
    
	}

	void push(const T& value)
	{
    
	}

	void pop()
	{
    
	}

private:
	Container _heap = { };
};

 

(2) empty, top 구현

동적 배열(vector)는 기본적으로 empty 함수를 가지고 있다.

그리고 동적 배열의 top은 배열의 가장 앞에 있는 인덱스 0으로 임의 접근 할 수 있다.

	bool empty()
	{
		return _heap.empty();
	}


	T& top()
	{
		return _heap[0];
	}

 

(3) push ( O(log N) )

힙 트리에서 데이터를 추가하는 것은 아래 조건이 만족되어야 한다.

- 가장 낮은 레벨에 먼저 추가

- 완전 이진 트리의 형태

- 부모 노드의 값이 자식 노드의 값보다 항상 커야 함

	void push(const T& data)
	{
		_heap.push_back(data);

		// 크기 비교
		int now = static_cast<int>(_heap.size()) - 1;

		while (now > 0) // 루트 노드까지 시도
		{
			//부모 노드와 비교해서 더 작으면 제자리에 남게 된다
			int next = (now - 1) / 2; // 부모 노드 인덱스
			if (_heap[now] < _heap[next])
				break;

			// 데이터 교체
			::swap(_heap[now], _heap[next]);
			now = next;
		}
	}

동적 배열의 끝에 데이터를 추가한다.

now는 지금 추가한 노드의 인덱스이다. 여기에서 루트의 인덱스가 0으로 시작하기 때문에, 배열의 size에서 1을 빼준 것이 추가한 노드의 인덱스가 된다.

데이터 교환은 자식 노드와 부모 노드의 데이터를 비교하고, 자식 노드가 더 크면 부모 노드로 올라가는 방식이므로

부모 노드와 자식 노드(추가한 노드)를 비교해서 더 작으면 break로 반복문을 종료시켜 제자리에 남게 한다.

아닌 경우에는 std::swap을 이용하여 두 노드의 데이터를 교환한다.

최종적으로는 now 인덱스에 부모 인덱스를 대입하여 마무리한다.

 

(4) pop ( O(log N) )

힙 트리의 pop은 최대값이기도 한 root의 데이터를 pop하는 것과 같다.

하지만 최상위에 root가 존재하고 있어야 하므로 leaf의 끝(마지막 인덱스)에 위치한 노드를 root로 대치시켜야 한다.

이후에는 push와는 반대로 root로 올라간 노드를 자식 노드들과 비교해서 힙 트리에 맞게 재정렬한다.

	void pop()
	{
		// 최상위 노드를 추출 후에 최하단 데이터를 위치시킴
		_heap[0] = _heap.back();
		_heap.pop_back(); // 최하단 노드 이동 후 제거

		int now = 0;

		while (true)
		{
			int left = 2 * now + 1;
			int right = 2 * now + 2;

			// 리프에 도달한 경우 체크
			if (left >= _heap.size())
				break;

			int next = now;

			// 왼쪽 비교
			if (_heap[next] < _heap[left])
				next = left;

			// 오른쪽 노드가 유효한지 확인 후 승자를 오른쪽과 비교
			if (right < _heap.size() && _heap[next] < _heap[right])
				next = right;

			// 왼쪽과 오른쪽 둘 다 현재 값보다 작으면 종료
			if (next == now) // 어떤 조건도 걸리지 않으면 next = now가 변하지 않음
				break;

			::swap(_heap[now], _heap[next]);
			now = next;
		}
	}

동적 배열의 back 함수를 이용하여 최하단 레벨의 마지막에 있던 노드를 최상위 root에 대입시킨다.

그리고 최하단 레벨의 마지막 노드를 pop_back으로 제거한다.

이후에는 root로 올라간 노드를 자식 노드 둘 중 더 큰 수와 비교하여 자리를 바꿔준다.

root의 인덱스는 0 이므로, now 인덱스는 0이다.

이전 포스트에서 부모 기준 왼쪽은 2 * i + 1, 오른쪽은 2 * i + 2 의 인덱스를 가진다는 것을 배웠다.

3-1. 트리 기초

이를 이용하여 left와 right를 만든다.

이후에는 트리의 끝에 도달하였는지 체크해준다. left 인덱스가 배열의 사이즈보다 크거나 같으면 break한다.

(사이즈는 1, 2, 3, 4, 5의 순서로 커지고, 인덱스는 0, 1, 2, 3, 4의 순서로 커진다는 것을 주의한다)

초기에는 next와 now 인덱스를 같게 설정해주고, 이후에 비교가 진행되면 next 인덱스와 left 또는 right 인덱스와 교체한다.

일련의 비교가 끝나면 now 노드와 next 노드의 값을 swap 하고, now 인덱스를 next 인덱스로 바꿔주어 그 다음 자식과의 비교를 시작하게 한다.

 

(5) 내림차순 혹은 오름차순 정렬

std::priority_queue는 세번째 인자로 내림차순(기본값)과 오름차순 정렬을 받을 수 있다.

이를 구현하기 위해서 PriorityQueue가 세번째 인자를 받도록 설정한다.

template<typename  T, typename Container = vector<T>, typename Predicate = less<T> > // 기본값은 벡터
class PriorityQueue
{ //~~~
private:
	Container _heap = { };
	Container _predicate = { };
};

 

그리고 데이터를 교환하는 식의 조건문을 수정한다.

	void push(const T& data)
	{ //~~
			//부모 노드와 비교해서 더 작으면 제자리에 남게 된다
			int next = (now - 1) / 2; // 부모 노드 인덱스
			if (_predicate(_heap[now], _heap[next]))
				break;

	void pop()
	{ // ~~~~
		while (true)
		{
			int left = 2 * now + 1;
			int right = 2 * now + 2;

			// 리프에 도달한 경우 체크
			if (left >= _heap.size())
				break;

			int next = now;

			// 왼쪽 비교
			if (_predicate(_heap[next],  _heap[left]))
				next = left;

			// 오른쪽 노드가 유효한지 확인 후 승자를 오른쪽과 비교
			if (right < _heap.size() && _predicate(_heap[next], _heap[right]))
				next = right;

이렇게 코드를 구성하면 이후에 세번째 인자를 std::less로 받으면 내림차순(기본값), std::greater로 받으면 오름차순이 된다.

 

(6) main

int main()
{
	PriorityQueue<int, vector<int>, less<int>> pq;

	pq.push(100);
	pq.push(300);
	pq.push(200);
	pq.push(500);
	pq.push(400);

	while (pq.empty() == false)
	{
		int value = pq.top();
		pq.pop();

		cout << value << endl;
	}

	return 0;
}

출력값 : 100, 200, 300, 400, 500

 

int main()
{
	PriorityQueue<int, vector<int>, greater<int>> pq;

	pq.push(100);
	pq.push(300);
	pq.push(200);
	pq.push(500);
	pq.push(400);

	while (pq.empty() == false)
	{
		int value = pq.top();
		pq.pop();

		cout << value << endl;
	}

	return 0;
}

출력값 : 500, 400, 300, 200, 100