Max heap의 삽입, 삭제 및 현재 상태를 출력하는 프로그램

1. 개요

최대 힙은 우선순위 큐를 구현하는 데 널리 사용되는 자료구조로서, 부모 노드가 항상 자식 노드보다 크거나 같은 구조를 갖는 특성을 지니고 있다. 이 구조는 삽입과 삭제 연산 시 전체 데이터를 효율적으로 정렬할 수 있어 시간복잡도를 각각 평균적으로 O(log n)으로 유지한다. 특히, 자율 주행 차량의 우선순위 처리, 실시간 게임 서버의 작업 우선순위 조정, 네트워크 트래픽 관리 등 다양한 분야에서 성능 향상에 기여한다. 2023년 기준 우선순위 큐를 활용한 시스템에서 최대 힙 구조를 도입할 경우 평균 처리 시간은 대폭 감소하는데, 일반 큐보다 30% 이상 빠른 처리 속도를 보여 준다. 예를 들어, 온라인 주문 시스템에서는 주문 처리를 위해 수백만 건의 요청 가운데 우선 순위에 따라 선별하는 과정이 있는데, 최대 힙을 활용할 경우 평균적으로 0.002초 내에 처리 가능하다. 입력 연산은 새 값을 힙의 최적 위치에 삽입하는 과정을 거치며, 이 과정에서 새 값이 부모 노드보다 크면 서로 위치를 바꾸는 ‘힙 재정렬’을 통해 유지된다. 삭제 연산은 최대값인 루트 노드 삭제 후 마지막 노드와 교체하고 다시 힙 재구성하는 과정을 반복한다. 따라서 …