자료구조 - PriorityQueue

우선순위 큐는 Heap의 구조를 이용해 정렬을 수행하는 이진 트리 구조이다. Heap은 원소를 삽입시 가장 큰 원소가 루트 노드에 오도록 노드의 위치를 재배열한다. 이 재배열을 하는 과정은 매번 O(logn)의 시간복잡도를 가지게 된다.

우선순위 큐를 구현하면서 가장 큰 두가지의 기능인 Push와 Pop의 기능을 생각해보자. Push 연산을 하게 되면 원소는 가장 마지막 Leaf노드의 다음 위치에 삽입되게 된다. 다음 위치에 삽입된 후 부모 노드의 크기 값과 비교하여 만약 부모원소보다 크다면 자리를 바꾸고 이 과정을 반복해 나가게 된다. 결국 가장 큰 원소라면 루트 노드에 위치하게 될 것이고 pop할시 루트 노드의 값을 출력해주기만 하면 된다.

pop한뒤 남아 있는 원소들의 정렬에 대해서는 가장 마지막에 위치하는 리프노드의 값을 루트노드로 옮기고 자식노드 들과 비교하여 자식노드가 더 크다면 위치를 바꾸어 준다. 자식이 두개 존재하는 경우 왼쪽, 오른쪽 둘 중 더 큰 자식과 자리를 바꾸어준다.

#include <cstdio>
#include <stdlib.h>

using namespace std;


class PriorityQueue
{
private:
	
	int max_size = 10;
	int size = 0;
	void allocate()
	{
		arr = (int*)malloc( sizeof(int)  * max_size );
	}
public:
	int* arr;
	PriorityQueue()
	{
		allocate();
	}
	PriorityQueue(int size)
	{
		max_size = size;
		allocate();
	}

	int getLeft(int n)
	{
		if (2 * n + 1 < size)
			return 2 * n + 1;
		else
			return -1;
	}
	int getRight(int n)
	{
		if (2 * n + 2 < size)
			return 2 * n + 2;
		else
			return -1;
	}

	int getParent(int n)
	{
		return (n - 1) / 2;
	}

	bool isFull()
	{
		return size == max_size;
	}
	bool isEmpty()
	{
		return size == 0;
	}

	void push(int a)
	{
		if (!isFull())
		{
			int current = size;
			int parent = getParent(current);

			arr[current] = a;
			while (arr[current] > arr[parent])
			{
				int temp = arr[current];
				arr[current] = arr[parent];
				arr[parent] = temp;

				current = parent;
				parent = getParent(current);
			}
			size++;
		}
	}
	int pop()
	{
		int target = arr[0];
		arr[0] = arr[--size];
		int current = 0;
	
		while (true)
		{
			int left_child = getLeft(current);
			int right_child = getRight(current);
			
			if (left_child != -1 && right_child != -1)
			{
				if (arr[current] < arr[left_child] || arr[current] < arr[right_child])
				{
					if (arr[left_child] < arr[right_child])
					{
						int temp = arr[current];
						arr[current] = arr[right_child];
						arr[right_child] = temp;
						current = right_child;
					}
					else
					{
						int temp = arr[current];
						arr[current] = arr[left_child];
						arr[left_child] = temp;
						current = left_child;
					}
				}
				else
					break;
			}
			else if (left_child != -1)
			{
				if (arr[current] < arr[left_child])
				{
					int temp = arr[current];
					arr[current] = arr[left_child];
					arr[left_child] = temp;
					current = left_child;
				}
				else
					break;
			}
			else
			{
				break;
			}
		}

		return target;
	}
};

void main()
{
	PriorityQueue pq;

	pq.push(324);
	pq.push(532);
	pq.push(3);
	pq.push(1023);
	pq.push(84);
	pq.push(23);
	pq.push(5);


	while (!pq.isEmpty())
	{
		printf("%d ", pq.pop());
	}
}