C++heapsort求前k个最小值
时间: 2024-10-19 07:15:09 浏览: 3
C++中的Heapsort算法是一种基于二叉堆数据结构的排序方法,特别适合用于找出一组元素中的前K个最小值。这里我们先简要介绍Heap这个数据结构:
- **堆**(Heap)是一个特殊的树形数据结构,通常分为最大堆(Max Heap)和最小堆(Min Heap)。最大堆的根节点总是比其他节点大,而最小堆则相反,根节点是最小的。
为了找到前K个最小值,我们可以采用“剩余堆”(Residual Heap)的概念,也就是在原始数组上构建一个最小堆,然后依次从堆顶取出元素并更新堆,直到取出了K个元素。以下是基本步骤:
1. 初始化:创建一个大小为K的小顶堆,将其初始化为空。
2. 建堆:遍历原始数组,将前K个元素插入到堆中,保证堆的性质。
3. 排序:从第K+1个元素开始,如果该元素小于当前堆顶(即最小堆),就将堆顶元素替换为该元素,并调整堆结构,使得堆顶始终是当前未考虑部分中的最小值。
4. 当遍历完整个数组时,堆中的前K个元素就是前K个最小值。
以下是一个简单的C++示例代码片段:
```cpp
#include <vector>
using namespace std;
void heapify(vector<int>& arr, int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest])
smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(arr[i], arr[smallest]);
heapify(arr, n, smallest);
}
}
void kthSmallest(vector<int>& arr, int k) {
int n = arr.size();
vector<int> minHeap(k);
// 将前k个元素直接插入堆
for (int i = 0; i < k; ++i)
heapify(minHeap, k, i);
for (int i = k; i < n; ++i) {
if (arr[i] < minHeap[0]) {
// 如果新元素比堆顶还小,替换堆顶并调整堆
minHeap[0] = arr[i];
heapify(minHeap, k, 0);
}
}
// 最终堆中的前k个元素就是前k个最小值
for (int i = 0; i < k; ++i)
cout << minHeap[i] << " ";
}
// 示例用法
int main() {
vector<int> arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int k = 3;
kthSmallest(arr, k);
return 0;
}
```
阅读全文