우선순위 큐

큐 - FIFO 가장 먼저 들어온 놈이 가장 먼저 나감

우선순위 큐 - 우선순위가 높은 놈 먼저 나감

 

우선순위

우선순위 큐를 어떻게 구현할까? 

우선순위가 가장 높은 애가 먼저 나간다고 했으니까
데이터를 삽입하거나 삭제할때마다 정렬을 해서 가장 앞에 있는 수를 내보내면 되지않을까?

그렇게 한다면 데이터 삽입 or 삭제시마다 정렬하는데 O(N^2)의 시간이 걸리기 때문에 안됨

 

우선순위 큐는 단순히 가장 큰 or 가장 작은 수를 맨 앞으로만 보내면 되기 때문에

모든 요소를 정렬을 하는 것이 아니라 루트가 가장 큰 값or 작은 값을 가지는 힙 트리를 이용하여 정렬을 함

그렇게 되면 삽입, 삭제하는 과정에서 O(logN)의 속도로 가장 우선순위가 높은 요소를 맨 앞으로 보낼 수 있음

 

힙 구조를 이용한 우선순위 선별은

부모 노드와의 비교만 하면 되기 때문에 크기가 N인 트리에서는 logN번의 비교만 하면 됨

class minHeap
{
public:
	void push(int n)
	{
		v.push_back(n);

		int curr = v.size() - 1;
        	// 부모노드 = (자식노드 - 1) / 2
		int parent = (curr - 1) / 2;

		// 부모 노드와의 비교
		while (parent >= 0)
		{
			// 부모 노드가 더 작다면 종료
			if (v[curr] >= v[parent])
				break;

			{ // 데이터 교환
				int temp = v[curr];
				v[curr] = v[parent];
				v[parent] = temp;
			}

			// 부모노드의 위치로 업데이트
			curr = parent;
			// 부모노드의 부모노드로 업데이트
			parent = (curr - 1) / 2;
		}
	}

	void pop()
	{
		if (v.empty()) return;

		// 끝에 있는 수를 맨 앞으로 옮기고
		int end = v.size() - 1;
		v[0] = v[end--];

		// 꼬리 자르기
		v.pop_back();

		int curr = 0;

		// 왼쪽 자식 = (부모노드 * 2) + 1
		int lChild = curr * 2 + 1;
		// 오른쪽 자식 = 왼쪽 자식 + 1
		int rChild = lChild + 1;
		int minChild;

		// 자식 노드와 비교 자식노드가 배열을 벗어나면 종료
		while (lChild <= end)
		{

			// 왼쪽,오른쪽 자식중 더 작은애를 선별
			if (rChild > end || v[lChild] < v[rChild])
				minChild = lChild;

			else
				minChild = rChild;

			// 현재 노드(부모)가 자식노드보다 작다면 종료
			if (v[curr] <= v[minChild])
				break;

			// 데이터 교환
			{
				int temp = v[curr];
				v[curr] = v[minChild];
				v[minChild] = temp;
			}

			// 현재 노도,자식노드 위치 업데이트
			curr = minChild;
			lChild = curr * 2 + 1;
			rChild = lChild + 1;
		}
	}

	int top()
	{
		if (v.empty()) return INT32_MAX;
		return v.front();
	}

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

	int size() { return v.size(); }

private:
	vector<int> v;
};