우선순위 큐

우선순위가 가장 높은 자료가 먼저 꺼내진다는 특징이 있다.

이런 큐를 구현하기 위해서는, 모든 원소를 순회하며 우선순위가 가장 높은 원소를 찾는 방법이 있다. 그러나 여기서는 힙이라는 단순한 구조의 이진 트리를 사용해서 새 원소를 추가하고 꺼내는 연산을 O(logN)에 수행한다.

힙

• 힙의 대소 관계 규칙
  • 부모 노드가 가진 원소는 자식 노드가 가진 원소보다 크거나 같다.
  • 왼쪽/오른쪽 자식에 대한 크기 제약은 없다.
• 힙의 모양 규칙
  • 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있어야 한다.
  • 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워져 있다.

배열을 이용한 힙의 구현

트리 상에서 아래와 같이 일차원 배열을 표현하게 되면, A[i] 노드에 대한 정보는 다음과 같이 정리할 수 있다.

왼쪽 자손은 A[2 x i + 1] 에 대응된다. 오른쪽 자손은 A[2 x i + 2] 에 대응된다. 부모 노드는 A[(i - 1)/2]에 대응된다.

이는 vector<int>heap으로 원소를 저장할 수 있다.

새 원소의 삽입

힙에서는 대소 관계 규칙보다 모양 규칙을 우선하기 때문에, 새 노드는 항상 heap[]의 가장 마지막에 추가된다. 그 다음, (1) 이 원소를 부모 노드와 비교해서, 부모 노드가 더 작다면 위치를 바꾼다. (2) 새롭게 들어온 원소가 더 크거나 같으면 루트에 도달할 때까지 반복한다.

void push_heap(vector<int>& heap, int newValue) {
	heap.push_back(newValue);

	int idx = heap.size() - 1;
	// 루트에 도달하거나, 새로 들어온 노드가 부모 노드보다 크면
	while (idx > 0 && heap[(idx - 1) / 2] < heap[idx]) {
		swap(heap[idx], heap[(idx - 1) / 2]);
		idx = (idx - 1) / 2; 
	}
}

최대 원소 꺼내기

힙의 최대 원소는 힙의 첫 원소에 있다. 이를 꺼내면 루트 노드는 빈 노드가 되고, 우리는 가장 마지막 노드를 가져와 여기에 넣어준다. (힙의 모양 규칙) 그 다음, 자식 노드와 비교해서 더 큰 원소를 선택해 바꿔준다. 이를 트리의 바닥까지 도달하거나, 두 자손이 자기 자신보다 작은 노드들만을 자식으로 가지고 있을 때까지 반복한다. (힙의 대소 관계 규칙)