堆 排 序

堆排序：完全二叉树结构的排序艺术（附完整项目下载）

一、算法原理可视化解析

1.1 堆结构核心概念

堆排序基于完全二叉树结构，分为两种类型：

• 大顶堆：父节点 ≥ 子节点（升序排序）
• 小顶堆：父节点 ≤ 子节点（降序排序）

关键特性：

• 叶子节点占总数约50%
• 最后一个非叶子节点索引：n/2-1（数组从0开始）

1.2 动态演示（文字版）

以数组 `` 为例：

初始状态：
3
/ \\
1 4
/ \\ / \\
1 5 9 2
/
6

构建大顶堆：
9
/ \\
6 5
/ \\ / \\
1 3 4 2
/
1

排序过程：
交换9与末尾元素 → 调整堆 → 重复操作直至有序

二、C++完整实现代码（带完整注释）

#include <iostream>
#include <vector>
using namespace std;

// 下沉操作（维护堆性质）
void siftDown(vector<int>& arr, int start, int end) {
int root = start;
while (true) {
int child = 2 * root + 1; // 左子节点
if (child > end) break; // 无子节点退出

// 选择较大子节点
if (child + 1 <= end && arr[child] < arr[child+1])
child++;

// 若父节点已最大则停止
if (arr[root] >= arr[child])
break;

// 交换父子节点
swap(arr[root], arr[child]);
root = child; // 继续下沉
}
}

// 构建大顶堆
void buildMaxHeap(vector<int>& arr) {
int n = arr.size();
// 从最后一个非叶子节点开始调整
for (int i = n/2 – 1; i >= 0; i—) {
siftDown(arr, i, n–1);
}
}

// 堆排序主函数
void heapSort(vector<int>& arr) {
int n = arr.size();

buildMaxHeap(arr); // 构建初始堆

// 逐个提取元素
for (int i = n–1; i > 0; i—) {
swap(arr[0], arr[i]); // 将最大值移到末尾
siftDown(arr, 0, i–1); // 调整剩余堆
}
}

// 打印数组辅助函数
void printArray(const vector<int>& arr) {
for (int num : arr) cout << num << "\\t";
cout << "\\n";
}

int main() {
vector<int> data = {12, 11, 13, 5, 6, 7};

cout << "排序前数组:\\n";
printArray(data);

heapSort(data);

cout << "\\n排序后数组:\\n";
printArray(data);

return 0;
}

代码说明：

• siftDown 实现堆调整核心逻辑
• 构建堆时从 n/2-1 开始逆序调整
• 排序阶段每次交换堆顶与末尾元素

三、分步执行解析（以测试用例为例）

3.1 初始状态

索引: 0 1 2 3 4 5 6
值: 12 11 13 5 6 7

3.2 构建大顶堆过程

3.3 排序阶段过程

四、算法流程图

#mermaid-svg-O1itCSUiEmqHYpkc{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-O1itCSUiEmqHYpkc .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-O1itCSUiEmqHYpkc .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-O1itCSUiEmqHYpkc .error-icon{fill:#552222;}#mermaid-svg-O1itCSUiEmqHYpkc .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-O1itCSUiEmqHYpkc .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-O1itCSUiEmqHYpkc .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-O1itCSUiEmqHYpkc .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-O1itCSUiEmqHYpkc .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-O1itCSUiEmqHYpkc .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-O1itCSUiEmqHYpkc .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-O1itCSUiEmqHYpkc .marker{fill:#333333;stroke:#333333;}#mermaid-svg-O1itCSUiEmqHYpkc .marker.cross{stroke:#333333;}#mermaid-svg-O1itCSUiEmqHYpkc svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-O1itCSUiEmqHYpkc p{margin:0;}#mermaid-svg-O1itCSUiEmqHYpkc .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-O1itCSUiEmqHYpkc .cluster-label text{fill:#333;}#mermaid-svg-O1itCSUiEmqHYpkc .cluster-label span{color:#333;}#mermaid-svg-O1itCSUiEmqHYpkc .cluster-label span p{background-color:transparent;}#mermaid-svg-O1itCSUiEmqHYpkc .label text,#mermaid-svg-O1itCSUiEmqHYpkc span{fill:#333;color:#333;}#mermaid-svg-O1itCSUiEmqHYpkc .node rect,#mermaid-svg-O1itCSUiEmqHYpkc .node circle,#mermaid-svg-O1itCSUiEmqHYpkc .node ellipse,#mermaid-svg-O1itCSUiEmqHYpkc .node polygon,#mermaid-svg-O1itCSUiEmqHYpkc .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-O1itCSUiEmqHYpkc .rough-node .label text,#mermaid-svg-O1itCSUiEmqHYpkc .node .label text,#mermaid-svg-O1itCSUiEmqHYpkc .image-shape .label,#mermaid-svg-O1itCSUiEmqHYpkc .icon-shape .label{text-anchor:middle;}#mermaid-svg-O1itCSUiEmqHYpkc .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-O1itCSUiEmqHYpkc .rough-node .label,#mermaid-svg-O1itCSUiEmqHYpkc .node .label,#mermaid-svg-O1itCSUiEmqHYpkc .image-shape .label,#mermaid-svg-O1itCSUiEmqHYpkc .icon-shape .label{text-align:center;}#mermaid-svg-O1itCSUiEmqHYpkc .node.clickable{cursor:pointer;}#mermaid-svg-O1itCSUiEmqHYpkc .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-O1itCSUiEmqHYpkc .arrowheadPath{fill:#333333;}#mermaid-svg-O1itCSUiEmqHYpkc .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-O1itCSUiEmqHYpkc .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-O1itCSUiEmqHYpkc .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-O1itCSUiEmqHYpkc .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-O1itCSUiEmqHYpkc .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-O1itCSUiEmqHYpkc .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-O1itCSUiEmqHYpkc .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-O1itCSUiEmqHYpkc .cluster text{fill:#333;}#mermaid-svg-O1itCSUiEmqHYpkc .cluster span{color:#333;}#mermaid-svg-O1itCSUiEmqHYpkc div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-O1itCSUiEmqHYpkc .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-O1itCSUiEmqHYpkc rect.text{fill:none;stroke-width:0;}#mermaid-svg-O1itCSUiEmqHYpkc .icon-shape,#mermaid-svg-O1itCSUiEmqHYpkc .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-O1itCSUiEmqHYpkc .icon-shape p,#mermaid-svg-O1itCSUiEmqHYpkc .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-O1itCSUiEmqHYpkc .icon-shape rect,#mermaid-svg-O1itCSUiEmqHYpkc .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-O1itCSUiEmqHYpkc .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-O1itCSUiEmqHYpkc .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-O1itCSUiEmqHYpkc :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

开始

数组长度>1?

构建大顶堆

结束

交换堆顶与末尾

堆大小减1

调整剩余堆

五、常见错误与调试技巧

5.1 典型错误案例

// 错误1：子节点索引越界
int child = 2*root; // 正确应为2*root+1

// 错误2：未处理相等元素
if (arr[root] > arr[child]) // 正确应包含>=

// 错误3：循环条件错误
while (child <= end) { // 正确应包含等号

5.2 调试技巧

void printHeap(const vector<int>& arr, int size) {
for(int i=0; i<size; i++) {
cout << arr[i] << " ";
if((i+1)%2 == 0) cout << "\\n"; // 每层换行
}
}

六、性能优化方向

6.1 优化策略对比

6.2 优化实现（迭代版本）

void heapSortIterative(vector<int>& arr) {
int n = arr.size();

// 构建堆
for (int i = n/2 – 1; i >= 0; i—) {
int j = i;
while (true) {
int child = 2*j + 1;
if (child >= n) break;
if (child+1 < n && arr[child] < arr[child+1])
child++;
if (arr[j] >= arr[child]) break;
swap(arr[j], arr[child]);
j = child;
}
}

// 排序
for (int i = n–1; i > 0; i—) {
swap(arr[0], arr[i]);
int j = 0;
while (true) {
int child = 2*j + 1;
if (child >= i) break;
if (child+1 < i && arr[child] < arr[child+1])
child++;
if (arr[j] >= arr[child]) break;
swap(arr[j], arr[child]);
j = child;
}
}
}

七、学习路线建议

八、完整项目资源

8.1 项目结构

HeapSort-Demo/
├── src/
│ ├── heap_sort.cpp # 基础实现
│ ├── iterative.cpp # 迭代版本
│ └── visualizer.cpp # 可视化模块
├── docs/
│ ├── algorithm_flow.md # 算法流程说明
│ └── error_cases.md # 常见错误网页
├── tests/
│ ├── test_cases.cpp # 测试用例
│ └── benchmark.cpp # 性能测试
└── README.md

8.2 下载链接

https://github.com/yourusername/heap-sort-demo
包含：

• 可直接编译的CMake项目
• 自动生成的堆结构变化动画
• 性能对比测试报告
• 交互式教学演示程序

九、扩展思考题

通过本文的学习，您已掌握堆排序的核心原理和实现技巧。建议从简单案例入手，逐步深入理解完全二叉树的结构特性，最终能够灵活运用并优化排序策略。编程能力的提升，正始于对基础算法的深刻理解！