赞
踩
堆排序可以看作顺序存储的完全二叉树。
堆排序属于选择排序的一种,
选择排序:每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列。
若n个关键字序列 L [ 1... n ] L[ 1...n] L[1...n]满足下面某一条性质,则称为堆(Heap) :
堆可以看作是一个完全二叉树的排列:
层序遍历以下二叉树:
1.常考的基本操作:
2.若完全二叉树中共有n个结点,则
根据大根堆的特性︰ 根 ≥ 左、右 根≥左、右 根≥左、右
//将以k 为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len) {
A[0] = A[k];//A[0]暂存子树的根结点
for (int i = 2 * k; i <= len; i *= 2) {
//汇key较大的子结点向下筛选
if (i < len && A[i] < A[i + 1])
i++;//取key较大的子结点的下标
if (A[0] >= A[i])break;//筛选结束
else {
A[k] = A[i];//将A[i]调整到双亲结点上
k = i;//修改k值,以便继续向下筛选
}
}
A[k] = A[0];//被筛选结点的值放入最终位置
}
//建立大根堆
void BuildMaxHeap(int A[], int len) {
for (int i = len / 2; i > 0; i--)//从后往前调整所有非终端结点
HeadAdjust(A, i, len);
}
//堆排序的完整逻辑
void HeapSort(int A[], int len) {
BuildMaxHeap(A, len);//初始建堆
for (int i = len; i > 1; i--) {// n-1趟的交换和建堆过程
swap(A[i], A[1]);//堆顶元素和堆底元素交换
HeadAdjust(A, 1, i - 1);//把剩余的待排序元素整理成堆
}
}
结论:
因此堆排序的时间为建堆的时间加上排序的时间:
根据代码:若左右孩子一样大,则优先和左孩子交换。
结论:不稳定。
寻找完全二叉树中相关结点的方法:
被删除的元素用堆底元素替代,然后让该元素不断“下坠”,直到无法下坠为止。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。