최대힙과 최소힙
2024. 7. 28. 22:07ㆍDataStructures
반응형
최대 힙(Max Heap)과 최소 힙(Min Heap)은 완전 이진 트리의 일종으로,
특정 규칙에 따라 정렬되는 데이터 구조입니다. 힙은 우선순위 큐를 구현하는 데 자주 사용됩니다.
최대 힙(Max Heap)
- 정의:
최대 힙은 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같은 이진 트리입니다.
따라서, 루트 노드는 항상 힙의 최대값을 가집니다. - 특징:
요소 추가 시, 새로운 요소는 트리의 가장 마지막 위치에 추가된 후, 부모 노드와 비교하며 올바른 위치로 이동합니다(상향 이동).
요소 삭제 시, 루트 노드가 제거되고 가장 마지막 노드가 루트에 위치한 후, 자식 노드와 비교하며 올바른 위치로 이동합니다(하향 이동). - 사용 예: 우선순위가 높은 작업을 빠르게 찾고 처리해야 하는 작업 스케줄러, 시뮬레이션, 네트워크 패킷 처리 등에 사용됩니다.
50
/ \
30 20
/ \ / \
15 10 8 5최소 힙(Min Heap)
- 정의:
최소 힙은 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 이진 트리입니다. 따라서, 루트 노드는 항상 힙의 최소값을 가집니다. - 특징:
요소 추가 시, 새로운 요소는 트리의 가장 마지막 위치에 추가된 후, 부모 노드와 비교하며 올바른 위치로 이동합니다(상향 이동).
요소 삭제 시, 루트 노드가 제거되고 가장 마지막 노드가 루트에 위치한 후, 자식 노드와 비교하며 올바른 위치로 이동합니다(하향 이동). - 사용 예: 다익스트라 알고리즘, A* 알고리즘 등 최단 경로 탐색 알고리즘, 그리고 각종 정렬 알고리즘에 사용됩니다.
5
/ \
10 8
/ \ / \
15 30 20 50힙의 연산
- 삽입(Insertion):
- 새로운 요소를 트리의 가장 마지막에 추가합니다.
- 최대 힙의 경우 부모 노드와 비교하여 자식 노드의 값이 더 크다면 서로 교환합니다.
최소 힙의 경우 자식 노드의 값이 더 작다면 교환합니다. - 올바른 위치가 될 때까지 이 과정을 반복합니다.
- 삭제(Deletion):
- 루트 노드를 제거합니다.
- 트리의 가장 마지막 요소를 루트 위치로 이동시킵니다.
- 최대 힙의 경우 자식 노드와 비교하여 자식 노드의 값이 더 크다면 서로 교환합니다.
최소 힙의 경우 자식 노드의 값이 더 작다면 교환합니다. - 올바른 위치가 될 때까지 이 과정을 반복합니다.
예제 코드
아래는 Java에서 PriorityQueue를 사용하여 최대 힙과 최소 힙을 구현하는 예제입니다.
import java.util.PriorityQueue;
import java.util.Collections;
public class HeapExample {
public static void main(String[] args) {
// 최소 힙 (기본 설정)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(5);
minHeap.add(15);
System.out.println("Min Heap:");
while (!minHeap.isEmpty()) {
System.out.println(minHeap.poll());
}
// 최대 힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(10);
maxHeap.add(5);
maxHeap.add(15);
System.out.println("Max Heap:");
while (!maxHeap.isEmpty()) {
System.out.println(maxHeap.poll());
}
}
}참고자료
반응형