1、堆排序定义
堆是一棵顺序存储的完全二叉树。
- 其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆。
- 其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆。
举例来说,对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时,称之为堆:
- Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
- Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
堆特征:
- 堆顶元素(完全二叉树的根)必为序列中n个元素的最小值或最大值
- 堆中任何一个结点的非空左右子树都是一个堆
- 根结点到任一个叶结点的每条路径上的结点值(关键字)都递减有序(或递增有序)
堆排序需解决的2个问题
1、堆构建:如何由一个无序序列建成一个堆?
2、堆排序:如何在输出堆顶元素之后,调整剩余元素,使之成为一个新的堆?
2、堆构建
对待排序的记录,建成相应的完全二叉树从无序序列的第个元素(即此无序序列对应的完全二叉树的最后一个非终端结点)起,至第一个元素止,进行反复筛选。
3、堆排序
定义:
将无序序列建成一个堆,得到关键字最小(或最大)的记录;
输出堆顶的最小(或最大)值后,使剩余的n-1个元素重又建成一个堆,则可得到n个元素的次小值;
重复执行,得到一个有序序列,这个过程叫堆排序。
排序过程:
1、输出堆顶元素之后,以堆中最后一个元素替代之;
2、然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换;重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为“筛选”。
4、算法实现
#include <iostream>
#include <vector>
using namespace std;
//构建大顶堆
void HeapAdjust(vector<int> &list, int parent, int length){
int temp = list[parent]; // temp保存当前父节点
int child = 2 * parent + 1; // 先获得左孩子
while (child < length){
// 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
if (child + 1 < length && list[child] < list[child + 1]){
child++;
}
// 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
if (temp >= list[child]){
break;
}
// 把孩子结点的值赋给父结点
list[parent] = list[child];
// 选取孩子结点的左孩子结点,继续向下筛选
parent = child;
child = 2 * parent + 1;
}
list[parent] = temp;
}
//堆排序
vector<int> HeadSort(vector<int> list){
int length = list.size();
// 循环建立初始堆
for (int i = length / 2 - 1; i >= 0; i--){
HeapAdjust(list, i, length);
}
// 进行n-1次循环,完成排序
for (int i = length - 1; i > 0; i--){
// 最后一个元素和第一元素进行交换
int temp = list[i];
list[i] = list[0];
list[0] = temp;
// 筛选 R[0] 结点,得到i-1个结点的堆
HeapAdjust(list, 0, i);
cout << "第" << length - i << "趟排序:";
for (int i = 0; i < list.size(); i++){
cout << list[i] << " ";
}
cout << endl;
}
return list;
}
void main(){
int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
cout << "排序前:";
for (int i = 0; i < test.size(); i++){
cout << test[i] << " ";
}
cout << endl;
vector<int> result;
result = HeadSort(test);
cout << "排序后:";
for (int i = 0; i < result.size(); i++){
cout << result[i] << " ";
}
cout << endl;
system("pause");
}
运行结果: