이 글에서는 시퀀스(배열)에 저장된 데이터 중 k번째로 큰 요소를 추출하는 C++ 프로그램을 살펴봅니다. 모든 데이터를 정렬한 뒤 인덱스로 접근하는 방식보다, 맥스 힙(Max-Heap)을 활용하면 전체 정렬 없이도 원하는 값을 효율적으로 얻을 수 있습니다. 이 기법의 시간 복잡도는 O(n + k·log(n))으로, k값이 작을수록 일반 정렬 방식보다 유리합니다.
알고리즘
- 힙의 최댓값(루트 노드)을 시퀀스의 마지막 위치로 보낸다.
- 남은 시퀀스를 대상으로 힙 재정렬(Heapify)을 수행한다.
- 위 과정을 총 'k'번 반복한다.
- 배열의 최종 상태를 출력한다.
- k번째 반복에서 추출된 힙의 최댓값을 결과로 출력한다.
핵심 아이디어는 간단합니다. 맥스 힙에서는 항상 최댓값이 루트에 위치하므로, 루트를 배열 끝과 교환하고 힙 크기를 하나 줄여가며 재정렬하면, 큰 값부터 차례대로 배열 뒤쪽에 배치됩니다. k번 반복하면 배열의 뒤에서 k번째 위치에 k번째로 큰 값이 놓이게 됩니다.
예제 코드
#include <iostream>
using namespace std;
void MaxHeapify(int a[], int i, int n) {
int j, t;
t = a[i];
j = 2*i;
while (j <= n) {
if (j < n && a[j+1] > a[j])
j = j+1;
if (t > a[j])
break;
else if (t <= a[j]) {
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = t;
return;
}
void Build_MaxHeapify(int a[], int n) {
int i;
for(i = n/2; i >= 1; i--)
MaxHeapify(a, i, n);
}
int main() {
int n, i, temp, k;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
n++;
int arr[n];
for(i = 1; i < n; i++) {
cout<<"Enter element "<<i<<": ";
cin>>arr[i];
}
cout<<"\nEnter the k value: ";
cin>>k;
Build_MaxHeapify(arr, n-1);
for(i = n-1; i >= n-k; i--) {
temp = arr[i];
arr[i] = arr[1];
arr[1] = temp;
MaxHeapify(arr, 1, i - 1);
}
cout<<"\nAfter max-heapify the given array "<<k<<" times the array state is: ";
for(i = 1; i < n; i++)
cout<<"->"<<arr[i];
cout<<"\n\nThe "<<k<<"th largest element is: "<<arr[n-k];
return 0;
}
코드 설명
MaxHeapify() 함수
특정 노드 i를 기준으로, 해당 노드의 값이 자식 노드들보다 작으면 자식과 교환하면서 아래로 내려보내는 함수입니다. 이 과정을 통해 i를 루트로 하는 부분 트리 전체가 맥스 힙의 성질(부모 ≥ 자식)을 만족하게 됩니다.
Build_MaxHeapify() 함수
입력 배열 전체를 맥스 힙으로 만드는 함수입니다. 마지막 부모 노드(n/2)부터 루트(1)까지 역순으로 MaxHeapify()를 호출하여 힙 구조를 완성합니다.
main() 함수
데이터 개수 n과 각 요소, 그리고 k값을 입력받은 뒤 힙을 생성합니다. 이후 루트(최댓값)와 배열 끝 요소를 교환하고 힙 크기를 줄여가며 k번 반복합니다. 반복이 끝나면 배열 상태와 함께 arr[n-k] 위치에 있는 값, 즉 k번째로 큰 요소를 출력합니다.
실행 결과
정렬할 데이터 요소의 개수 입력: 5
요소 1 입력: 20
요소 2 입력: 10
요소 3 입력: 30
요소 4 입력: 70
요소 5 입력: 60
k 값 입력: 2
주어진 배열을 2회 맥스 힙화한 후 배열 상태: ->30->20->10->60->70
2번째로 큰 요소: 60
시간 복잡도 분석
- 힙 생성: O(n)
- k번 추출 및 재정렬: 추출 1회당 O(log n)이므로 총 O(k·log n)
- 전체 복잡도: O(n + k·log(n))
전체 정렬에 필요한 O(n·log n)보다 k가 작은 경우 훨씬 효율적이므로, '상위 k개' 형태의 문제에서 널리 활용되는 접근법입니다.