[자료구조] 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)란?

---

이미지 출처: https://1.bp.blogspot.com/-OqvvBv9eLGo/Xu4VcEKKgZI/AAAAAAAAAWE/6Nw_9n6gaAEzQNACA2DWxI4yGvfIH0qQQCK4BGAsYHg/s565/priqueu.png

큐의 구조를 따르지만(FIFO, First In First Out) 우선 순위를 결정하고 높은 우선순위를 가진 요소를 먼저 꺼내서 처리하는 자료구조이다. 우선순위큐는 내부적으로 힙(Heap)으로 구성되어 이진트리의 구조로 이루어져있다. 따라서 O(N log N)의 시간복잡도를 가진다.

 

Heap이란?

이미지 출처 포함

Heap은 완전 이진트리로 구현되었으며 우선순위 큐를 위한 자료구조이다. 부모 노드의 값은 자식 노드의 값보다 크거나(Max Heap) 작아야(Min Heap)한다. 이러한 구조를 이용하여 최댓값과 최솟값을 빠르게 찾아낼 수 있다.

• 힙은 배열로 구현된다. 편의상 0번 인덱스는 사용하지 않는다.
• 왼쪽, 오른쪽 노드의 위치가 대소 관계를 반영하지 않는다. 즉 왼쪽 노드와 오른쪽 노드는 부모 노드보다 값이 작으면 된다. 
• 힙트리에서는 중복값을 허용한다.
• 최대 힙(Max heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리
• 최소 힙(Min heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리

Heap의 인덱스 구하기

Heap은 완전 이진트리로 구현되어있기때문에, 노드의 개수를 알면 트리의 구조를 파악할 수 있다.

현재 노드 번호가 i라면, 아래와 같이 노드의 인덱스를 구할 수 있다.

• 현재 노드의 부모 노드: (i - 1) / 2
• 현재 노드의 왼쪽 자식 노드: i * 2 + 1
• 현재 노드의 오른쪽 자식 노드: i * 2 + 2

* 완전 이진 트리(Complete binary tree)란? 

각 노드가 최대 2개의 자식 노드를 가지며 마지막 레벨을 제외한 모든 노드는 왼쪽에서 오른쪽으로 완전히 채워져있는 트리이다. 

Heap에 데이터 삽입, 삭제

데이터 삭입, 삭제시 Heapfify 알고리즘을 이용하여 Heap의 성질을 유지한다.

• 데이터 삽입시, 맨 마지막 노드로 추가한 뒤, Heapfify 알고리즘을 이용해서 리프노드에서 루트 노드까지 정렬을 한다.
• 데이터 삭제시, 루트 노드를 맨 마지막 노드로 교체한뒤, 마지막 노드를 삭제한다. 이후 Heapfify 알고리즘을 이용해서 루트노드부터 리프노드까지 정렬을 한다.

우선순위 큐 구현

• 우선순위 큐에 저장하는 객체는 Comparable Interface를 필수로 구현해야한다. 해당 객체에서 우선순위 조건을 반환하면 PriorityQueue가 우선순위가 높은 객체를 선별한다.
• 우선순위 큐의 내부 동작 방식은 힙 정렬 참고

class Node implements Comparable<Node> {
	private int weight;
	private int index;

	public Node(int weight, int index) {
		this.weight = weight;
		this.index = index;
	}

	@Override
	public int compareTo(Node node) {
	// 우선순위 큐의 기준을 가중치로 제공
		return Integer.compare(this.weight, node.weight);
	}
}
    
    
PriorityQueue<Node> queue = new PriorityQueue<>();
    
queue.add(new Node(0, 21)); // 삽입 성공시 true 반환, 실패시 IllegalStateException 발생
queue.offer(new Node(0, 21)); // 삽입 성공시 true, 실패시 false 반환

Node node = queue.poll(); // 첫번째 값을 반환하고 제거함. 비어있다면 null 반환
queue.remove(); // 첫번째 값을 제거함. 비어있다면 예외 발생
queue.peek(); // 첫번째 값을 반환함. 제거는 하지 않음

queue.clear(); // 큐 초기화