Heap 자료구조
Heap이란?
Java에서 Heap 자료구조는 우선순위 큐(Priority Queue)로 구현되며, 부모 노드의 값이 자식 노드보다 항상 크거나 작은 특성을 가지고 있는 완전 이진 트리이다. Max Heap과 Min Heap으로 나눠진다.
우선순위 큐(Priority Queue)란?
우선순위 큐(Priority Queue)는 큐(Queue) 자료구조의 일종으로, 일반적인 큐와는 다르게 요소들이 삽입되는 순서가 아닌, 각 요소의 우선순위에 따라 처리되는 자료구조이다. 큐에서는 먼저 들어온 요소가 먼저 나가는 선입선출 방식이지만, 우선순위 큐에서는 우선순위가 높은 요소가 먼저 나가게 된다.
- 최소 힙(Min Heap): 우선순위가 작은 요소부터 제거된다.
- 최대 힙(Max Heap): 우선순위가 큰 요소부터 제거된다.
PriorityQueue는 기본적으로 Min Heap으로 동작하지만, Comparator를 제공하여 Max Heap으로도 사용할 수 있다.
Heap 선언
Min Heap 선언
PriorityQueue<Integer> minHeap = new PriorityQueue<>();Max Heap 선언
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());커스텀 객체 우선순위 설정하기
PriorityQueue를 사용할 때 객체 타입을 우선순위 큐에 삽입할 경우, Comparator를 사용하여 객체의 우선순위를 설정할 수 있다.
숫자나 문자열 같은 자연 순서가 정의된 객체를 사용할 때는 별도로 Comparator를 설정하지 않아도 된다.
예를 들어, Person 클래스의 우선순위를 age로 설정하는 방법은 아래와 같다.
import java.util.PriorityQueue;
import java.util.Comparator;
class Person {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return name + " (" + age + ")";
}
}
public class CustomPriorityQueue {
public static void main(String[] args) {
PriorityQueue<Person> pq = new PriorityQueue<>(new Comparator<Person>() {
@Override
public int compare(Person p1, Person p2) {
// 오름차순 정렬
return Integer.compare(p1.age, p2.age);
// 내림차순 정렬
// return Integer.compare(p2.age, p1.age);
}
});
pq.offer(new Person("Alice", 30));
pq.offer(new Person("Bob", 25));
pq.offer(new Person("Charlie", 35));
// 나이가 적은 사람부터 출력
System.out.println(pq.poll()); // Bob (25)
System.out.println(pq.poll()); // Alice (30)
System.out.println(pq.poll()); // Charlie (35)
}
}Heap 주요 메서드
offer(E e): 힙에 요소를 추가한다.poll(): 힙에서 우선순위가 가장 높은 요소를 제거하고 반환한다.
Min Heap에서는 가장 작은 값을, Max Heap에서는 가장 큰 값을 반환한다.peek(): 힙에서 우선순위가 가장 높은 요소를 제거하지 않고 반환한다. 힙이 비어 있으면 null을 반환한다.isEmpty(): 힙이 비어 있는지 확인한다. 비어있으면 true, 비어있지 않으면 false를 반환한다.size(): 힙에 있는 요소의 개수를 반환한다.contains(Object o): 힙에 특정 요소가 포함되어 있는지 확인한다. 해당 요소가 있으면 true, 없으면 false를 반환한다.clear(): 힙을 초기화한다.
Min Heap 동작
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// offer() 메서드: 요소 추가
minHeap.offer(0);
minHeap.offer(3);
minHeap.offer(2);
minHeap.offer(7);
// poll() 메서드: 힙에서 우선순위가 가장 높은 요소를 제거하고 반환한다.
int element = minHeap.poll();
System.out.println(element); // 0
// peek() 메서드: 힙에서 우선순위가 가장 높은 요소를 제거하지 않고 반환한다.
int peek = minHeap.peek();
System.out.println(peek); // 2
// contains() 메서드: 특정 요소 포함 여부 확인
System.out.println(minHeap.contains(3)); // true
System.out.println(minHeap.contains(1)); // false
// size() 메서드: 힙의 크기 확인
int size = minHeap.size();
System.out.println(size); // 3
// isEmpty() 메서드: 힙이 비어 있는지 확인
System.out.println(minHeap.isEmpty()); // false;
// clear() 메서드: 모든 요소 제거
minHeap.clear();
System.out.println(minHeap); // []
// isEmpty() 다시 확인
System.out.println(minHeap.isEmpty()); // true;Max Heap 동작
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// offer() 메서드: 요소 추가
maxHeap.offer(0);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(7);
System.out.println(minHeap);
// poll() 메서드: 힙에서 우선순위가 가장 높은 요소를 제거하고 반환한다.
int element = maxHeap.poll();
System.out.println(element); // 7
// peek() 메서드: 힙에서 우선순위가 가장 높은 요소를 제거하지 않고 반환한다.
int peek = maxHeap.peek();
System.out.println(peek); // 3
// contains() 메서드: 특정 요소 포함 여부 확인
System.out.println(maxHeap.contains(3)); // true
System.out.println(maxHeap.contains(1)); // false
// size() 메서드: 힙의 크기 확인
int size = maxHeap.size();
System.out.println(size); // 3
// isEmpty() 메서드: 힙이 비어 있는지 확인
System.out.println(maxHeap.isEmpty()); // false;
// clear() 메서드: 모든 요소 제거
maxHeap.clear();
System.out.println(maxHeap); // []
// isEmpty() 다시 확인
System.out.println(maxHeap.isEmpty()); // true;