问题一
问题描述
在计算机科学与社会生活中，经常涉及到要求前K个元素即top-k的问题，请给出不同策解决这一问题，并对比分析
问题分析
本题假设取最大的k个元素
首先最直接的想法就是先进行排序，再取前k个元素，选取快速排序作为本题的排序算法，时间复杂度是$O(nlogn)$，然后选择前k个元素，总时间复杂度是$O(nlogn)$，以下是快速排序的实现。
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) >> 1];
while (i <= j) {
while (arr[i] > pivot) {
i++;
}
while (arr[j] < pivot) {
j--;
}
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
if (left < j) {
quickSort(arr, left, j);
}
if (i < right) {
quickSort(arr, i, right);
}
}方法二采用堆的数据结构，采用先进先出的策略，建立一个最小堆存取最大的k个元素，对整个序列进行遍历，将序列中的前k个元素压入堆中，从第k+1个元素开始进行队首元素进行判定，若当前元素大于队首元素，将队首弹出，将当前元素加入队列中；否则不进行任何操作。遍历结束后，反转顺序，打印输出。以下是堆排序的实现
void MaxKElements(int arr[], int n, int k) {
priority_queue<int, vector<int>, greater<int>> MinHeap;
for (int i = 0; i < n; i++) {
if (i < k) {
MinHeap.push(arr[i]);
}
else {
if (arr[i] > MinHeap.top()) {
MinHeap.pop();
MinHeap.push(arr[i]);
}
}
}
vector<int> res;
while (!MinHeap.empty()) {
res.push_back(MinHeap.top());
MinHeap.pop();
}
reverse(res.begin(), res.end());
for (int i = 0; i < k; i++) {
cout << res[i] << " ";
}
cout << endl;
}方法三是对方法一的改进，将快速排序改成快速选择算法，找到第k大的元素，然后对整个序列进行遍历，筛选出大于第k大元素的元素组成数组，到这里为止，时间复杂度是$O(n)$，但是还要进行降序输出，因此进行排序，在下列实现中，调用了sort函数，但是排序消耗的时间是$O(klogk)$。
int QuickSelect(vector<int>& nums, int left, int right, int k) {
int pivot = nums[left];
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] <= pivot) {
j--;
}
nums[i] = nums[j];
while (i < j && nums[i] >= pivot) {
i++;
}
nums[j] = nums[i];
}
nums[i] = pivot;
if (i == k - 1) {
return pivot;
}
else if (i < k - 1) {
return QuickSelect(nums, i + 1, right, k);
}
else {
return QuickSelect(nums, left, i - 1, k);
}
}
void MaxKElements(vector<int>& nums, int k) {
int kth = QuickSelect(nums, 0, nums.size() - 1, k);
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] >= kth) {
res.push_back(nums[i]);
}
}
sort(res.begin(), res.end(), greater<int>()); // 降序排序
res.resize(k); // 取前k个元素
for (int i = 0; i < k; i++) {
cout << res[i] << " ";
}
cout << endl;
}算法实现与分析
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
void QuickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) >> 1];
while (i <= j) {
while (arr[i] > pivot) {
i++;
}
while (arr[j] < pivot) {
j--;
}
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
if (left < j) {
QuickSort(arr, left, j);
}
if (i < right) {
QuickSort(arr, i, right);
}
}
void MaxKElements(int arr[], int n, int k) {
priority_queue<int, vector<int>, greater<int>> MinHeap;
for (int i = 0; i < n; i++) {
if (i < k) {
MinHeap.push(arr[i]);
}
else {
if (arr[i] > MinHeap.top()) {
MinHeap.pop();
MinHeap.push(arr[i]);
}
}
}
vector<int> res;
while (!MinHeap.empty()) {
res.push_back(MinHeap.top());
MinHeap.pop();
}
reverse(res.begin(), res.end());
for (int i = 0; i < k; i++) {
cout << res[i] << " ";
}
cout << endl;
}
int QuickSelect(vector<int>& nums, int left, int right, int k) {
int pivot = nums[left];
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] <= pivot) {
j--;
}
nums[i] = nums[j];
while (i < j && nums[i] >= pivot) {
i++;
}
nums[j] = nums[i];
}
nums[i] = pivot;
if (i == k - 1) {
return pivot;
}
else if (i < k - 1) {
return QuickSelect(nums, i + 1, right, k);
}
else {
return QuickSelect(nums, left, i - 1, k);
}
}
void MaxKElements(vector<int>& nums, int k) {
int kth = QuickSelect(nums, 0, nums.size() - 1, k);
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] >= kth) {
res.push_back(nums[i]);
}
}
sort(res.begin(), res.end(), greater<int>()); // 降序排序
res.resize(k); // 取前k个元素
for (int i = 0; i < k; i++) {
cout << res[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = { 5, 3, 8, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
QuickSort(arr, 0, n - 1);
cout << "前2个元素是";
for (int i = 0; i < 2; i++) {
cout << arr[i] << " ";
}
cout << endl;
int arr1[] = { 5, 3, 8, 4, 2 };
MaxKElements(arr1, 5, 2);
vector<int> arr2 = { 5, 3, 8, 4, 2 };
MaxKElements(arr2, 2);
}实现：
方法一的时间复杂度是$O(nlogn)$
方法二的时间复杂度是$O(nlogk)$
方法三的时间复杂度是$O(n+klogk)$
问题二
问题描述
请用递归方式实现堆排序，并进行性能分析
算法实现与分析
#include<iostream>
#include<vector>
using namespace std;
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l<n && arr[l]>arr[largest]) {
largest = l;
}
if (r<n && arr[r]>arr[largest]) {
largest = r;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void HeapSort(vector<int>& arr, int n) {
for (int i = (n >> 1) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
heapify(arr, i, 0);
}
}
int main() {
vector<int> arr = { 5,3,8,4,2 };
HeapSort(arr, 5);
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
cout << endl;
}实现：
对于递归方式的堆排序，每次对子树进行heapify操作的时间复杂度是$O(logn)$，对于每一棵包含n个结点的完全二叉树，高度为$logn$，因此堆排序的时间复杂度是$O(nlogn)$。
递归方式的堆排序使用了函数递归调用，每次递归都会将一部分数据压入栈中，栈的深度等于堆的高度，最坏情况下堆的高度是$logn$，空间复杂度是$O(logn)$。
