우선순위 큐(Priority Queue)

이번에 공부할 자료구조는 우선순위 큐이다. 우선순위 큐는 데이터들이 우선순위를 가지며, 우선순위가 높은 데이터가 먼저 출력된다. 또한, 스택이나 큐도 우선순위 큐를 사용하여 얼마든지 구현할 수 있다.

우선순위 큐는 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 트리에서 언급한 힙(Heap)이다. 힙은 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료 구조이다. 힙은 일종의 반정렬 상태를 유지한다. 이를 활용하여 우선순위 큐를 구현한다. 힙은 삽입, 삭제 연산이 O(log n)의 시간 복잡도를 가질 만큼 훌륭하다.

힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조이다. 간단히 말하면 부모 노드의 키값이 자식 노드의 키값보다 항상 큰(작은) 이진 트리를 말한다. 또한, 이진 탐색 트리와 달리 중복된 값을 허용한다.

힙는 최대, 최소 두 가지 종류의 힙 트리가 존재한다.

1. 최대 힙 (Max Heap)

부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리
Key(Parent Node) >= Key(Child Node)

2. 최소 힙 (Min Heap)

부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리
Key(Parent Node) <= Key(Child Node)

힙은 완전 이진 트리이기 때문에 각각의 노드에 차례대로 번호를 붙일 수 있다. 이 번호를 배열의 인덱스로 생각하면 굉장히 편하기 때문에 배열을 이용하여 구현을 주로 한다. 보통 루트 노드의 인덱스를 0이 아닌 1로 두고 구현을 한다. 그 이유는 1로 두고 다음과 같이 시작하면 자식, 부모 노드의 인덱스에 접근이 수월하기 때문이다.

왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2

힙의 삽입 연산은 다음과 같다.

새로운 데이터를 힙의 마지막 노드에 삽입한다.
힙 트리의 성질을 만족할 때까지 새로운 노드와 부모 노드를 비교하여 힙을 재구성한다.

힙의 삭제 연산은 다음과 같다.

루트 노드를 삭제한다.
힙의 마지막 노드를 루트 노드에 삽입한다.
힙 트리의 성질을 만족할 때까지 자식 노드와 비교하여 힙을 재구성한다.

우선순위 큐(Priority Queue)는 JAVA에선 간단하게 라이브러리를 추가하여 별다른 구현 없이 생성할 수 있다. 기본적으로 최소 힙(Min Heap) 구조로 구현되어 있다.

import java.util.PriorityQueue;
PriorityQueue<"자료형"> "우선순위 큐 이름" = new PriorityQueue<>();

다른 조건으로 우선순위 큐를 사용할 때는 Comparable or Comparator 인터페이스를 이용하여 우선순위 조건을 부여한다.

Comparable : 객체 간의 일반적인 정렬이 필요할 때, Comparable 인터페이스를 확장해서 정렬의 기준을 정의하는 compareTo() 메서드를 구현한다.
Comparator : 객체 간의 특정한 정렬이 필요할 때, Comparator 인터페이스를 확장해서 특정 기준을 정의하는 compare() 메서드를 구현한다.

다음은 간단하게 1차원 배열로 구현한 최대 힙이다.

class MyMaxHeap {
	int[] arr;
	int heapSize;
	
	public MyHeap(int size) {
		heapSize = 0;
		arr = new int[size];
	}
	
	public void insert(int data) {
		if (heapSize > arr.length) {
			System.out.println("Heap is Full!");
			return;
		}
		
		int start = ++heapSize;
		arr[start] = data;
		while (start > 1 && arr[start / 2] < arr[start]) {
			int temp = arr[start / 2];
			arr[start / 2] = arr[start];
			arr[start] = temp;
			start /= 2;
		}
	}
	
	public int remove() {
		if (heapSize < 1) {
			System.out.println("Heap is Empty!");
			return 0;
		}
		
		int ret = arr[1];
		arr[1] = arr[heapSize];
		arr[heapSize--] = 0;
		
		int start = 1;
		while (start <= heapSize) {
			if (arr[start * 2] > arr[start] && arr[start * 2] >= arr[start * 2 + 1]) {
				int tmp = arr[start * 2];
				arr[start * 2] = arr[start];
				arr[start] = tmp;
				start *= 2;
			} else if (arr[start * 2 + 1] > arr[start] && arr[start * 2] < arr[start * 2 + 1]){
				int tmp = arr[start * 2 + 1];
				arr[start * 2 + 1] = arr[start];
				arr[start] = tmp;
				start *= 2;
				start++;
			} else {
				break;
			}
		}
		
		return ret;
	}
}