赞
踩
完全二叉树中所有非终端节点的值均不大于(或不小于)其左、右孩子节点的值称为堆。若在输出堆顶的最小或最大元素后,使得剩余n-1个元素的序列又建成一个堆,则得到n个元素中的次小值或次大值,这样反复执行,遍得到一个序列,这样的过程称为堆排序。堆排序最坏情况下,其时间复杂度为O(nlogn);
堆排序需要解决两个问题:
(1)如何由一个无序的序列建成一个堆。
(2)如何在输出顶点元素后,调整剩余元素成为一个新的堆。
从一个无序的序列建成堆就是一个反复筛选的过程。若序列看作是一个完全二叉树,则从最后一个非终端节点n/2开始进行筛选。假设输出堆顶元素之后,以堆中最后一个元素替换,则需从顶点元素开始,自上而下的进行调整即可。
void heapAdjust(ElementType list[],int s,int m){//大顶堆,传入list除堆顶元素s外,其他节点必须已经满足堆的定义
ElementType rc = list[s];//保存堆顶元素,然后为其查找插入位置
for(int i = 2*s;i <= m;i*=2){//遍历子节点,从左节点开始
if(i < m && list[i + 1] > list[i]) i++; // 比较左右节点大小,若右节点(2*s + 1)大于左节点,则调整右子数,反之,则调整左子树
if(rc > list[i]) break;//父节点最大,则无需调整,已是大顶堆
list[s] = list[i];//将较大的子节点和父节点交换,因为破坏了子数,所以继续调整
s = i;//记录当前空出的位置,然后继续向下调整
}
list[s] = rc;//插入位置
}
void heapSort(ElementType list[],int n){
for(int i = n / 2;i > 0;i--){//1.建成大顶堆
heapAdjust(list,i,n);
}
for(int i = n ; i > 1; i--){
ElementType temp = list[1];//将最后一个节点和对顶元素交换,列表从1下标开始
list[1] = list[i];
list[i] = temp;
heapAdjust(list,1,i - 1);//重新调整为大顶堆,从堆顶开始
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。