1 算法描述
堆是一个完全二叉树，堆的存储可以使用数组（正是因为堆是一个完全二叉树才可以这么存储），堆分为大根堆和小根堆。
大根堆的定义：该完全二叉树的父节点都比子节点大。
小根堆的定义：该完全二叉树的父节点都比子节点小。
堆排序的思想是先构建一个大根堆（对父节点进行），然后开始排序过程。
堆排序过程：
- 1 建堆：对父节点依次进行下滤操作，得到大根堆。
- 2 排序：
- 2.1 vector压入大根堆的末尾叶子节点
- 2.2 将大根堆的末尾叶节点与根节点交换，执行下滤操作
- 2.3 重复2.2的操作N次，直到数组有序
2 算法模版
堆排序的模版分为两个部分：
- 1 建立大根堆
- 2 排序
下滤操作：
void heapify(vector &array, int n, int i) {
int largest = i;
int lson = 2 * i + 1;
int rson = 2 * i + 2;
if (lson < n && array[largest] < array[lson])
largest = lson;
if (rson < n && array[largest] < array[rson])
largest = rson;
if (largest != i) {
swap(array[largest], array[i]);
heapify(array, n, largest);
}
} 建立大根堆和排序：
void heapSort(vector &array, int n) {
// 1 建堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// 2 排序
for (int i = n - 1; i > 0; i--) {
swap(array[i], array[0]);
heapify(array, i, 0);
}
} 3 整体算法
// 1 堆一定是一个完全二叉树
// 2 堆序性 = 大根堆（大小小） + 小根堆（小大大）
// 3 堆的存储: 层数遍历的编号作为数组的索引
// 4 堆的操作: 下滤:将root节点与最大的子节点比较，小于则交换，直到叶节点为止,上滤相反
// 5 堆的建立: 自顶向下(上滤)
// 6 堆的应用: 优先队列，堆排序（将优先队列的最小值依次弹出即可）
void heapify(vector &array, int n, int i) {
int largest = i;
int lson = 2 * i + 1;
int rson = 2 * i + 2;
if (lson < n && array[largest] < array[lson])
largest = lson;
if (rson < n && array[largest] < array[rson])
largest = rson;
if (largest != i) {
swap(array[largest], array[i]);
heapify(array, n, largest);
}
}
void heapSort(vector &array, int n) {
// 1 建堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// 2 排序
for (int i = n - 1; i > 0; i--) {
swap(array[i], array[0]);
heapify(array, i, 0);
}
}
int main() {
vector array = {12, 98, 34, 24, 53, 0, 100, 5, 65, 99};
for (auto a : array) {
cout << a << endl;
}
cout << "start quickSort" << endl;
heapSort(array, array.size());
for (auto a : array) {
cout << a << endl;
}
return 0;
}