힙 자료구조란

정의

힙(Heap)은 이진 트리(Binary Tree) 기반의 자료 구조로서, 최댓값이나 최솟값을 빠르게 찾기 위해 사용됩니다.

종류

힙은 일반적으로 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 나뉩니다. 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 값을 가지며, 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 가집니다.

사용해야 할 때

다음과 같은 경우에 힙을 사용할 수 있습니다:

• 우선순위 큐(Priority Queue)를 구현해야 할 때
• 최댓값 또는 최솟값을 빠르게 찾아야 할 때
• 정렬된 상태를 유지하며 요소를 삽입하거나 삭제해야 할 때

예제

다음은 자바에서 힙 자료구조를 사용하는 예제 코드입니다:

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // Integer 타입의 최소 힙 생성
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 요소 추가
        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(10);
        minHeap.offer(7);
        minHeap.offer(3);

        // 힙에서 요소 추출 (최솟값부터 추출)
        while (!minHeap.isEmpty()) {
            int element = minHeap.poll();
            System.out.println(element);
        }
    }
}

위의 예제에서는 PriorityQueue<Integer>를 사용하여 정수값을 저장하는 최소 힙을 생성하고, offer() 메서드를 사용하여 요소를 추가합니다. 그리고 poll() 메서드를 사용하여 힙에서 요소를 추출하여 출력합니다. 실행 결과는 다음과 같습니다:

2
3
5
7
10

위의 예제에서는 작은 값부터 추출되므로 오름차순으로 정렬된 결과를 확인할 수 있습니다.