면접 문제: 쌓 기 순 서 를 이용 하여 n 개의 숫자 에서 앞의 top - k 큰 숫자 를 찾 습 니 다.

\ # 더미 로 정렬 (최소 더미): top - k 최대 숫자
제목: top - k 알고리즘, n 개 크기 의 배열 에서 k 개의 가장 큰 숫자 를 찾 아 출력 합 니 다.
입력: 배열 크기 n = 10;k 의 값 은 5 입 니 다.배열 은 9, 8, 3, 2, 10, 20, 13, 1, 5 이다.
출력: 20, 13, 10, 9, 8
사고: 1. k 개의 최소 더 미 를 유지 합 니 다. 만약 에 새로 들 어 온 숫자 가 최소 더 미 를 가 진 뿌리 노드 보다 크 면 뿌리 노드 를 새로 들 어 온 숫자 로 바 꾼 다음 에 최소 더 미 를 조정 합 니 다.2. k 개의 큰 숫자 를 찾 은 후에 k 개의 큰 숫자 를 한 번 씩 쌓 아서 정렬 합 니 다. 우리 가 가장 작은 숫자 를 만 들 었 기 때문에 쌓 아서 정렬 한 서열 은 바로 오름차 순 입 니 다. P: 쌓 아서 정렬 하 는 평균 시간 복잡 도 는 O (n * logn) 입 니 다. 빠 른 것 보다 빠 른 것 은 최 악의 경우 (배열 의 순서 가 있 음) 시간 복잡 도 는 O (n ^ 2) 입 니 다.

/*
  ：      ：
	  1、      n      top-k      
	  2、       ，  k       
*/
#include
#include
using namespace std;

void headAdjust(vector &arr, int start, int end){
	//i         
	int i = start * 2 + 1;
	while (i <= end){
		//          
		if (i + 1 <= end&&arr[i] > arr[i + 1]){
			//          ， i     
			i++;
		}
		if (arr[start] > arr[i]){
			swap(arr[start], arr[i]);
			start = i;
			i = 2 * start + 1;
		}
		else{
			break;
		}
	}
}

void heapSort(vector &arr, int start, int end){
	//                    ，          
	for (int i = (end - 1) / 2; i >= 0; i--){
		headAdjust(arr,i,end);
	}
	//       ，        ，             ，           ，                  。
	for (int i = end; i-1 >= 0; i--){
		swap(arr[i], arr[0]);
		headAdjust(arr, 0, i-1);
	}
}

int main(){
	//     k       
	int k;
	int n;
	cin >> n;
	cout << "top-k   ：";
	cin >> k;
	cout << "      ，    top-" << k << "  " << endl;
	vector arr(k,0);
	for (int i = 0; i < n; i++){
		if (i > k - 1){
			int temp;
			cin >> temp;
			if (temp > arr[0]){
				arr[0] = temp;
				headAdjust(arr, 0, k - 1);
			}
		}
		else{
			int temp;
			cin >> temp;
			arr[i] = temp;
			if (i == k - 1){
				//     
				for (int j = (k - 1 - 1) / 2; j >= 0; j--) {
					heapAdjust(arr, j, k-1);
				}
			}
		}
	}
	//         
	heapSort(arr, 0, k - 1);
	for (int i = 0; i < arr.size(); i++){
		cout << arr[i];
		if (i < arr.size()-1){
			cout << " ";
		}
	}
	system("pause");
	return 0;
}