堆排序问:
首先堆是建立在一个完全二叉树上的.
完全二叉树:只能最后一个层次的最右边结点为空的二叉树或是一棵满二叉树,这样的树称为完全二叉树.
那么这种数据结构是如何将数组转换成树的呢?思路又是怎么的呢?把这个数组按照从上到下从左到右的顺序写成一棵
比如 0 1 2 3 4 5 6 7 8 9 10 可以转换成按照上面的思路转换成这种结构
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
看见没....每一行就相当于树中的一层.并且每一个元素的索引还可以用来标识树中对应结点的位置,那么我们怎么来实现这个算法呢.
首先在一棵树中我们要能通过一个父结点来找到他的儿子.还能通过儿子找到他的父亲..来看看用数组中怎么实现的吧.
比如拿双亲0来说吧...我们要使用数组中的这个索引来找到对应到树中的儿子.. 我们将索引表示为 i;
那么0的儿子为 2*i+1, 右儿子是2*i+2....那么我们有一个结点的过引值,如果来找到他的父亲呢?
父亲的过引为 (孩子索引值-1)/2.因为在c语言里面移位去处比较高效,所以我们可以将上面两个表达示进行优化.
求孩子: (i<<1)+1 //左移就是操作数乘上2的幂次
求父亲:(孩子索引-1)>>1 //右移就是操作数除以2 的幂次.就是这样简单
我要们怎么实现这个出堆函数呢?下面来讲一下思路:
出操作需要的条件是这棵树必需是已树是一个堆.只能这样才能保证每次出堆操作后会生成一个新的有效堆.
首先队头元素出堆.然后们于队尾的元素变成队头.
将这个新队头元素逐层向下比较直到叶子结点.
//设堆的容量为heapsize并且肯定是满的,如果您看不懂我写的东西 ,很正常,因为我不会,你可以买本数据结构再仔细看一下.
//堆的条件就是根结点一定要大于双亲结点
//这个是堆化函数,用来将数组维护成一个堆.
void heapfiy(int index)
{
int leftchild, rightchild, largest;
leftchild = (index<<1)+1; //计算左孩子索引
int temp = arr[index]; //保存新的根结点,用于下面的单赋值交换.
while(leftchile<heapsize)
{
if((rightchile = leftchild+1)>heapsize) //判断是否存大右子树
{
largest = leftchild;
}
else
{
largest = (arr[leftchild > arr[rightchild])? leftchild:rightchild;
}
//找到值最大的孩子
if(temp>=arr[largest]) //如果新的结点值刚好大于孩子结点中的最大的一个话,那么退出环
{
break;
}
arr[index] = arr[largest]; //移动值,更新索引.
index = largest;
leftchild = (index<<1)+1;
}
arr[index] = temp;
}
入堆的操作呢.是这样进行的.
每一个将入堆的数都是从最后一个结点位置过去的.
the last index;
void enheap(int newelement)
{
int temp = newelement;
for(;i>0 && temp>arr[(i-1)>>1]; i = (i-1)>>1) ////进行这个循环还要知道只有树的根结点没有双亲,其余结点有且公有一个双亲
{
arr[i] = arr[(i-1)>>1]; //小元素向下移,实时记录索引.
}
}