以大根堆为例，堆排序过程如下：

1. 将初始待排序关键字序列(R0,R1....Rn-1)构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素与堆尾元素交换，堆的长度减1， 此时得到新的无序区和新的有序区；
3. 由于交换后新的堆顶可能违反堆的性质， 因此需要对当前无序区调整为新堆；
4. 不断重复过程2和3直到有序区的元素个数为n-1，则整个排序过程完成

堆的基本操作分为向上调整和向下调整，利用向上调整操作构建堆，堆顶元素和堆尾交换后，堆长度减1，利用向下调整操作从堆顶开始调整生成新堆。

#include <iostream>
using namespace std;inline void swap(int arr[], int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;
}// 向上调整堆	：从堆尾开始向堆顶调整
// 	arr	: 堆数组指针
//	n	： 堆尾元素位置
void shiftUp(int arr[], int n) {if (n < 1) {return;}int b = (n - 1) / 2;int a = n;while (a > 0) {if (arr[a] > arr[b]) {swap(arr, a, b);a = b;b = (b - 1) / 2;} else {break;}}
}// 向下调整堆	：从堆顶开始向堆尾调整
// 	arr	: 堆数组指针
//	n	： 堆尾元素位置
void shiftDown(int arr[], int n) {if (n < 1) {return;}int a, b = 0;int maxLeaf = (n - 1) / 2;while (b <= maxLeaf) {a = 2 * b + 1;if (a < n && arr[a] < arr[a + 1]) {a++;}if (arr[b] < arr[a]) {swap(arr, b, a);b = a;} else {break;}}
}// 堆排序算法
//	arr	： 待排序的数组指针
//	len	： 数组长度
void heapSort(int* arr, int len) {int index;// 构建堆for (index = 1; index < len; index++) {shiftUp(arr, index);}// 调整堆for (index = len - 1; index > 0;) {swap(arr, 0, index);index--;shiftDown(arr, index);}
}// 测试算法
int main() {int arr[] = { 213, 43, 43, 123, 45, 52, 67, 234, 452, 5, 67 };int len = 11;cout << "Before sorting:" << endl;for (int i = 0; i < len; i++) {cout << arr[i] << "\t";}cout << endl << endl;heapSort(arr, len);cout << "After Sorting:" << endl;for (int i = 0; i < len; i++) {cout << arr[i] << "\t";}cout << endl;return 0;
}