您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# C++怎么实现堆排序
## 1. 堆排序概述
堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的比较排序算法。它由J. W. J. Williams在1964年提出，是一种不稳定的排序算法，平均和最坏时间复杂度均为O(n log n)。
### 1.1 基本概念
- **堆**：一种特殊的完全二叉树，满足堆属性：
- 最大堆：父节点值 ≥ 子节点值
- 最小堆：父节点值 ≤ 子节点值
- **完全二叉树**：除最后一层外，其他层节点都完全填满，且最后一层节点尽可能靠左
### 1.2 算法特点
- 时间复杂度：构建堆O(n)，每次调整O(log n)，总复杂度O(n log n)
- 空间复杂度：O(1)（原地排序）
- 不稳定排序：相同元素可能改变相对位置
## 2. 堆排序原理
### 2.1 算法步骤
1. **构建初始堆**：将无序数组构建成最大堆/最小堆
2. **交换堆顶元素**：将堆顶元素（最大值/最小值）与末尾元素交换
3. **调整堆**：缩小堆范围，重新调整剩余元素为堆结构
4. **重复步骤2-3**：直到堆中只剩一个元素
### 2.2 关键操作
- **Heapify（堆化）**：维护堆性质的核心操作
- **建堆（Build Heap）**：从最后一个非叶子节点开始自底向上堆化
## 3. C++实现详解
### 3.1 基础实现
```cpp
#include <iostream>
#include <vector>
// 堆化函数（最大堆）
void heapify(std::vector<int>& arr, int n, int i) {
int largest = i; // 初始化最大元素为当前节点
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点存在且大于当前最大节点
if (left < n && arr[left] > arr[largest])
largest = left;
// 如果右子节点存在且大于当前最大节点
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果最大节点不是当前节点，交换并递归调整
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// 堆排序主函数
void heapSort(std::vector<int>& arr) {
int n = arr.size();
// 构建最大堆（从最后一个非叶子节点开始）
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 逐个提取元素
for (int i = n - 1; i > 0; i--) {
// 移动当前根到末尾
std::swap(arr[0], arr[i]);
// 调整剩余堆
heapify(arr, i, 0);
}
}
template <typename T, typename Compare>
void heapify(std::vector<T>& arr, int n, int i, Compare comp) {
int target = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && comp(arr[target], arr[left]))
target = left;
if (right < n && comp(arr[target], arr[right]))
target = right;
if (target != i) {
std::swap(arr[i], arr[target]);
heapify(arr, n, target, comp);
}
}
template <typename T, typename Compare = std::less<T>>
void heapSort(std::vector<T>& arr, Compare comp = Compare()) {
int n = arr.size();
// 建堆
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i, comp);
// 提取元素
for (int i = n - 1; i > 0; i--) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0, comp);
}
}
void iterativeHeapify(std::vector<int>& arr, int n, int i) {
while (true) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest == i) break;
std::swap(arr[i], arr[largest]);
i = largest;
}
}
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 建堆 | O(n) | 非直观的线性时间复杂度 |
| 每次堆调整 | O(log n) | 树的高度 |
| 总体排序 | O(n log n) | 建堆 + n次调整 |
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>
// 此处插入前面实现的heapSort函数...
// 生成随机数组
std::vector<int> generateRandomArray(int size) {
std::vector<int> arr(size);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(1, 10000);
for (int i = 0; i < size; ++i) {
arr[i] = dis(gen);
}
return arr;
}
// 测试排序正确性
void testCorrectness() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
std::vector<int> expected = arr;
heapSort(arr);
std::sort(expected.begin(), expected.end());
if (arr == expected) {
std::cout << "排序正确性测试通过\n";
} else {
std::cout << "排序正确性测试失败\n";
}
}
// 性能测试
void testPerformance() {
const int size = 1000000;
std::vector<int> arr = generateRandomArray(size);
auto arr2 = arr; // 复制用于std::sort
auto start = std::chrono::high_resolution_clock::now();
heapSort(arr);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> elapsed = end - start;
std::cout << "堆排序耗时: " << elapsed.count() << " 秒\n";
start = std::chrono::high_resolution_clock::now();
std::sort(arr2.begin(), arr2.end());
end = std::chrono::high_resolution_clock::now();
elapsed = end - start;
std::cout << "std::sort耗时: " << elapsed.count() << " 秒\n";
}
int main() {
testCorrectness();
testPerformance();
return 0;
}
堆排序在交换堆顶元素和末尾元素时，可能会改变相同元素的相对位置。例如： 原始序列：3a, 2, 3b 建堆后：3a, 2, 3b 第一次交换后：3b, 2, 3a（3a和3b顺序改变）
看似每个节点堆化时间为O(log n)，总时间应为O(n log n)，但实际上： - 大部分节点高度低 - 精确计算可得总操作为O(n)
template <typename T>
class PriorityQueue {
private:
std::vector<T> heap;
void heapifyUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap[parent] >= heap[index]) break;
std::swap(heap[parent], heap[index]);
index = parent;
}
}
void heapifyDown(int index) {
int size = heap.size();
while (true) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
if (left < size && heap[left] > heap[largest])
largest = left;
if (right < size && heap[right] > heap[largest])
largest = right;
if (largest == index) break;
std::swap(heap[index], heap[largest]);
index = largest;
}
}
public:
void push(const T& value) {
heap.push_back(value);
heapifyUp(heap.size() - 1);
}
void pop() {
if (heap.empty()) return;
heap[0] = heap.back();
heap.pop_back();
heapifyDown(0);
}
const T& top() const {
return heap.front();
}
bool empty() const {
return heap.empty();
}
};
std::vector<int> findTopK(const std::vector<int>& nums, int k) {
PriorityQueue<int> pq;
for (int num : nums) {
pq.push(num);
if (pq.size() > k) {
pq.pop();
}
}
std::vector<int> result;
while (!pq.empty()) {
result.push_back(pq.top());
pq.pop();
}
std::reverse(result.begin(), result.end());
return result;
}
堆排序是一种高效的通用排序算法，特别适合需要保证最坏情况性能的场景。虽然在实际应用中可能不如快速排序快，但其O(n log n)的时间复杂度和O(1)的空间复杂度使其在某些场景下不可替代。理解堆排序不仅有助于掌握一种排序算法，更是学习优先级队列、堆数据结构等重要概念的基础。
通过本文的C++实现，我们深入探讨了： 1. 堆排序的基本原理和实现方法 2. 多种实现方式的代码示例 3. 算法的时间/空间复杂度分析 4. 实际应用场景和优化方向 5. 相关的扩展应用
希望这篇全面的指南能帮助您彻底掌握堆排序在C++中的实现和应用。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。