인하대 데이터구조 9주차 Homework3 Maxheap

1. Problem definition

최대 힙(Max Heap)은 완전 이진 트리의 일종으로, 각 노드가 그 자식 노드들보다 크거나 같아야 하는 특성을 가진다. 이 구조는 우선순위 큐와 같은 다양한 데이터 처리 문제에서 널리 사용된다. 최대 힙에서 루트 노드는 항상 가장 큰 값을 가지며, 이를 통해 최대 값을 O(의 시간 복잡도로 접근할 수 있다. 최대 힙의 주요 연산에는 삽입, 삭제(최대 값 제거), 최대 값 추출이 있으며, 각 연산은 평균적으로 O(log n)의 시간 복잡도를 가진다. 최대 힙은 배열을 사용하여 구현할 수 있다. 이 경우, 배열의 인덱스와 트리 구조 간의 관계를 통해 간편하게 자식 노드를 접근할 수 있다. 예를 들어, 루트 노드가 배열의 첫 번째 인덱스(0)라면, 해당 노드의 왼쪽 자식 노드는 2배 한 인덱스(와 오른쪽 자식 노드는 2배 한 인덱스에 1을 더한 것(으로 쉽게 계산할 수 있다. 이러한 인덱스 계산 방식은 힙의 저장 공간에서 메모리 낭비를 최소화하고, 접근 속도를 증가시킨다. 최대 힙은 다양한 응용 프로그램에서 활용도가 높다. 가장 대표적인 예가 우선순위 큐이다. 우선순위 큐는 요소가 삽입될 때마다 우선순위에 따라 정렬되어야 하는데, 최대 힙…