> [!warning] > 이 페이지는 아직 미완성입니다. ### 기본 개념 [[Heap]] ## 문제 해결 방법 Max/Min Heap 만들기 - 우선 주어진 n개의 원소들 사이의 어떤 비교 관계를 만들어 주어진 데이터를 Max/Min Heap으로 바꾼다. 한 번에 원소 하나씩 추출하기 - 한 번에 원소를 하나씩 추출하면 그 때 가장 우선순위가 높은 원소를 뽑을 수 있다. 그래서 Min Heap을 만들었다면 매번 가장 작은 원소를 뽑기 때문에 결과적으로 뽑은 순서대로 원소들이 자동으로 정렬된다. ## 증명 이 증명은 우선순위를 고려해 트리를 구성하는 함수에 대한 증명으로, 역시나 수학적 귀납법으로 해결한다. 우선 Loop invariant라는 것을 설정하는데, 반복문이 실행될 때마다 바뀌는 어떤 값을 명시한 것이다. 여기서는 i = 1, 2, 3, …, n/2-1, n/2 일때, i+1을 max heap의 루트로 설정한다. 초기값은 i = n/2로, 이는 1번부터 차례대로 할 경우 정렬을 할 때마다 기존의 트리가 구현된 배열을 조정해야 하기 때문이다. 그 다음, loop invariant를 i = k로 바꿔 i = k에서 이 함수가 Heap Property를 유지한다고 가정하고, i = k-1에서도 마찬가지라는 것을 증명한다. 우선 i = k-1에서 루트는 k가 된다. 그리고 k는 이미 Heap Property를 만족한 상태로 정렬되어 있다. 그렇기 때문에 k를 루트로 하는 트리는 Heap Property를 만족한다. 그렇기 때문에 우선순위를 고려해 k-1번째 원소를 삽입하면, 트리는 Heap Property를 만족한다. ## 시간 복잡도 노드를 넣을 때 우선순위를 고려해 배치하고, 노드를 빼낼 때는 뺴고 나서 우선순위대로 트리를 다시 정렬하면 된다. 우선순위를 고려해 노드를 배치하는 것은 맨 뒤에 새 노드를 추가한 다음, 우선순위를 고려해 인덱스를 2로 나눠가면서 하고, 트리를 우선순위대로 다시 정렬하는 과정은 맨 마지막 원소를 위로 올린 다음 인덱스를 2씩 곱하면서 조정한다. 따라서 한 개의 노드를 하나 넣거나 뺄 때 모두 O(logn)의 평균 시간 복잡도를 가진다. 정확히는 연산이 실행될 당시의 트리의 높이인 d에 비례하며, 모든 순간 트리가 가지는 높이를 더해주면 된다.