최대 힙(Max Heap)이란?
최대 힙(Max Heap)은 완전 이진 트리(complete binary tree)의 한 종류로, 모든 단계에서 부모 노드(루트 노드)의 값이 자식 노드의 값보다 크거나 같은 구조를 가지는 자료구조입니다. 이러한 특성 덕분에 트리 전체에서 가장 큰 값이 항상 루트에 위치하게 되며, 최댓값 조회를 O(1)의 시간 복잡도로 수행할 수 있습니다.
자바에서는 별도의 힙 구현 없이 표준 라이브러리인 PriorityQueue 클래스를 활용하면 손쉽게 최대 힙을 사용할 수 있습니다. 기본적으로 PriorityQueue는 최소 힙(min heap)으로 동작하지만, 생성자에 Collections.reverseOrder()를 전달하면 내림차순 정렬 기준이 적용되어 최대 힙처럼 동작합니다.
예제 코드
아래는 라이브러리 함수를 사용해 최대 힙을 구현한 자바 코드입니다.
import java.util.*;
public class Demo{
public static void main(String args[]){
PriorityQueue<Integer> my_p_queue = new PriorityQueue<Integer>(Collections.reverseOrder());
my_p_queue.add(43);
my_p_queue.add(56);
my_p_queue.add(99);
System.out.println("The elements in the priority queue are : ");
Iterator my_iter = my_p_queue.iterator();
while (my_iter.hasNext())
System.out.println(my_iter.next());
my_p_queue.poll();
System.out.println("After removing an element using the poll function, the queue elements are :");
Iterator<Integer> my_iter_2 = my_p_queue.iterator();
while (my_iter_2.hasNext())
System.out.println(my_iter_2.next());
Object[] my_arr = my_p_queue.toArray();
System.out.println("The array representation of max heap : ");
for (int i = 0; i < my_arr.length; i++)
System.out.println("Value: " + my_arr[i].toString());
}
}실행 결과
The elements in the priority queue are : 99 43 56 After removing an element using the poll function, the queue elements are : 56 43 The array representation of max heap : Value: 56 Value: 43
코드 설명
Demo라는 이름의 클래스에는 main 함수가 포함되어 있습니다. main 함수 내부에서는 먼저 PriorityQueue 인스턴스가 생성되며, 생성 시 Collections.reverseOrder()를 인자로 전달해 최대 힙으로 동작하도록 설정했습니다.
이후 add 함수를 사용해 43, 56, 99 세 개의 정수 요소를 큐에 추가합니다. 요소 추가 시 힙 특성에 따라 내부적으로 재정렬이 이루어지므로, 가장 큰 값인 99가 항상 우선순위가 가장 높게 유지됩니다.
그다음 Iterator를 정의해 우선순위 큐에 담긴 요소들을 순회하며 출력합니다. 참고로 이터레이터 순회 순서는 힙의 내부 배열 구조를 따르기 때문에 반드시 내림차순으로 출력되는 것은 아니라는 점에 유의해야 합니다.
poll 함수는 우선순위가 가장 높은 요소, 즉 최댓값을 큐에서 제거하고 반환하는 역할을 합니다. 이 예제에서는 99가 제거되며, 제거 후 남은 요소들은 다시 이터레이터를 통해 화면에 출력됩니다. 마지막으로 toArray 함수를 호출해 힙의 내부 데이터를 배열 형태로 변환한 뒤, 각 값을 순차적으로 출력합니다.
주요 메서드 정리
- add(): 큐에 요소를 추가하며, 시간 복잡도는 O(log n)입니다.
- poll(): 최댓값(우선순위가 가장 높은 요소)을 제거하고 반환하며, 시간 복잡도는 O(log n)입니다.
- peek(): 요소를 제거하지 않고 최댓값만 확인할 때 사용합니다.
- iterator(): 큐의 요소를 순회할 수 있는 이터레이터를 반환합니다.
- toArray(): 큐의 요소들을 배열 형태로 변환합니다.
이처럼 자바의 PriorityQueue를 활용하면 최대 힙을 직접 구현하지 않고도 간결하고 안정적인 코드로 우선순위 기반 데이터 처리를 할 수 있습니다.