[Data Structure] 비선형 구조 - 힙 (Heap), 우선순위 큐(Priority Queue)

01. 힙 (Heap)

힙은 완전 이진 트리의 일종으로, 우선순위 큐를 구현하기 위해 사용되는 자료구조이다.

시간복잡도는 O(log N) 최대값 또는 최소값 일 경우 O(1)

- 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다.

 

01-1. 힙의 특성

힙은 각 노드가 하위 노드보다 큰(또는 작은) 우선순위를 가진다.

최대 힙(Max Heap)에서는 부모 노드가 자식 노드보다 항상 크고, 최소 힙(Min Heap)에서는 부모 노드가 자식 노드보다 항상 작다.

 

01-2. 힙 구현 방법

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

https://yozm.wishket.com/magazine/detail/2312/

 

---

02. 우선순위 큐 (PriorityQueue)

자바에서는 PriorityQueue 클래스를 사용하여 힙을 쉽게 구현할 수 있다.

가장 우선순위가 높은 값을 빼네는 pop(), 자료를 추가하는 push() 연산이 존재한다.

import java.util.PriorityQueue;

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 최소 힙
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
System.out.println(minHeap.poll()); // 1

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 최대 힙
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
System.out.println(maxHeap.poll()); // 5