우선순위 큐

우선순위 큐의 정의

큐 : pop하면 먼저 들어간 원소가 나온다
우선순위 큐 : pop하면 가장 높은 우선순위를 가진 원소가 나온다

우선순위 큐의 기능

우선순위 큐는 힙을 이용하여 구현하며, 원소 삽입, 우선순위가 가장 높은 원소 조회, 우선순위가 가장 높은 원소 삭제 이렇게 세 가지의 기능을 제공한다.

• 원소 삽입 : O(logN)
• 우선순위가 가장 높은 원소 조회 : O(1)
• 우선순위가 가장 높은 원소 삭제 : O(logN)

힙(heap)이란?

균형 이진 트리 구조이며, 최댓값이나 최솟값을 찾기 쉬운 자료구조
힙의 종류로는 최대힙과 최소힙이 있다.

• 최대힙 : 트리의 루트가 가장 큰 값을 갖는 힙
• 최대힙 : 트리의 루트가 가장 작은 값을 갖는 힙

힙은 아래 그림과 같이 왼쪽에서부터 원소를 채우는 형태여서 항상 균형을 갖춘 균형 이진 트리일 수 있다

Insert

원소 삽입
위 그림과 같은 순서대로 삽입을 하고, 힙의 성질을 만족하지 않으면 부모와 자리를 바꾸어서 힙의 성질을 유지하도록 한다.

이 그림과 같이 최소힙에 8을 삽입하는 경우, 힙의 성질을 만족하지 못하게 된다.
따라서 8의 부모인 55와 자리를 바꾸고, 루트인 15와도 자리를 바꾸어서 힙의 성질을 유지할 수 있도록 한다.
이처럼 삽입의 경우, 최악의 경우에도 트리의 높이만큼만 확인을 하면되므로 시간 복잡도는 O(logN)이다.

Fetch

우선순위가 가장 높은 원소 조회
즉, 최소힙에서 최솟값, 최대힙에서 최댓값의 확인은 그냥 트리의 루트 원소를 확인하면 된다. 따라서 시간 복잡도는 O(1)이다.

Erase

우선순위가 가장 높은 원소 삭제
트리 구조에서 가장 마지막 위치와 루트의 자리를 바꾼다. 그 이후에 삽입에서와 같이 힙의 성질을 유지할 수 있도록 자리를 바꾸어준다.
최소힙의 경우에는 루트에 가장 작은 값이 와야 하므로 루트와 그의 자식들 중에 더 작은 값을 갖는 원소와 자리를 바꾼다. 두 자식이 모두 루트보다 더 클 때까지 이 작업을 반복한다.
삽입과 동일하게 최악의 경우에도 트리의 높이만큼만 확인을 하면되므로 시간 복잡도는 O(logN)이다.

구현

힙은 배열로 대응시켜서 구현할 수 있다.

push

최소 힙에 원소 x를 삽입하는 경우
배열의 끝에 원소를 삽입하고 힙 성질을 만족할 때까지 부모 원소와 값을 비교하며 값을 변경한다.

void push(int x) {
	arrSize += 1;
	arr[arrSize] = x;

	int idx = arrSize;
	while (idx > 1) {
		if (arr[idx] < arr[idx / 2]) { // 부모가 더 크면 교환
			swap(idx, idx/2);
			idx /= 2;
		}
		else
			break;
	}
}

top

최소 힙에서 가장 작은 원소를 확인하는 경우
트리의 루트를 확인하면 되므로, 배열의 첫번째 원소를 확인하면 된다

int top() {
	return arr[1];
}

pop

최소 힙에서 가장 작은 원소를 제거하는 경우
트리의 루트를 가장 마지막 원소로 바꾼다.
그 후에 힙의 성질을 보존하기 위해서 자식 원소와의 크기를 비교하면서 비교한다.
현재 확인하는 원소가 트리의 리프인지 주의하여 확인해야 한다.

void pop() {
	if (arrSize == 0)
		return;

	arr[1] = arr[arrSize];
	arrSize -= 1;
	
	int cur = 1;
	while (cur * 2 <= arrSize) { // 리프인지 확인!
		int leftChild = cur * 2;
		int rightChild = cur * 2 + 1;
		int minChild = leftChild;
		if (arr[leftChild] > arr[rightChild])
			minChild = rightChild;
		if (arr[cur] > arr[minChild]) {
			swap(cur, minChild);
			cur = minChild;
		}
		else
			break;
	}
}

STL

priority_queue STL은 기본적으로 내림차순 정렬으로, 최대 힙이 적용된다
최소 힙을 사용하려면, 오름차순으로 정렬될 수 있도록 greater를 사용하여 선언할 수 있다.

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