本文共 2633 字,大约阅读时间需要 8 分钟。
由于堆也被引申为Java中的垃圾收集存储机制,在本文中使用堆的定义仅为堆数据结构。
完全二叉树的定义为:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
堆是一个数组,也可以被看作一个近似的完全二叉树。对堆可以分为两类:
左边的即为大顶堆,右边的即为小顶堆,堆也可用作构造一种有效的优先序列。
这里使堆元素从数组A[1]开始填充,即A[0]作为哨兵用于其他用途,即该树的根结点为A[1]。
如果按照层序遍历(即从上到下,从左到右)的方式对结点从1开始编号,则结点满足如下的关系:
堆排序:它的基本思想是,将待排序的序列构成一个大顶堆。此时,整个序列n的最大值即为堆顶的根结点。将根结点输出(其实就是将其与堆数组的最末尾元素进行交换,此时最末尾元素即为最大值,),然后将剩下的n-1个元素重新构成一个大顶堆,然后重复操作,便能得到一个有序的输出序列。
现在,基于上面的解释,我们需要完成两个任务即能解决问题:
//第一个for循环完成构建大顶堆的目标,第二个for循环即完成任务2,输出堆顶元素及调整void HeapSort(int arr[],int n){ int i; for(i = n/2;i > 0;--i)//由完全二叉树可知,从1开始排序的n个结点的二叉树,它的最小(最下层最右)的非叶子结点为n/2 //i值的递减操作表示,非叶子结点从下到上执行HeapAdjust函数,确保每一子树的根结点都是该子树中的最大值 HeapAdjust(arr,i,n);//把无序序列构建为一个大顶堆 for(i = n;i > 1;--i) { swap(arr,1,i);//将堆顶元素输出 HeapAdjust(arr,1,i-1);//将A[1...i-1]重新调整为大顶堆 }}
这里可以看出父结点和子结点的关系,即父结点为i,左右子树结点为2i,2i+1。
//对于数组中A[1.....n]都满足堆的定义(A[0]为哨兵位)//将序列调整为一个大顶堆void HeapAdjust(int arr[],int s,int m){ int temp,j; temp = arr[s]; //存储父结点s的值,同时也可用于与子结点比较大小 for(j = 2 * s;j <= m;j *= 2)//由二叉树的性质可知,左子结点为父结点下标的2倍,j *= 2即按照两倍的关系寻找一系列子结点 { if(j < m && arr[j] < arr[j+1])//j不为最后一个结点(即存在右兄弟) ++j;//确定左右子树中的较大值下标 if(temp > arr[j])//子结点并没有大于父结点的值,直接跳出循环 break; arr[s] = arr[j];//执行到这里,表示存在比父结点大的值,执行交换操作 s = j; //将子结点下标保留 } arr[s] = temp;//插入,将父结点临时存储在temp中的值赋给子结点下标,完成交换值操作 //下次循环,根结点将作为子结点时参与HeapAdjust函数,函数将当前子树中的最大值交换到父结点。}
第一次循环,父结点i为4。确保最末端(最下层最右)的父结点为当前子树的最大值
i- -为3,第2次循环由于父结点为最大值,没有变化。
i值递减为2,使最大值到父结点
i值为1,将结点3的值交换到结点1,注意,此时s的值为子结点3的下标。对结点3而言,满足2*3<总结点数,故再次进入循环判断结点3(作为根结点)是否为最大值。
最终形成大顶堆。
void swap(int arr[],int i,int j)//输出顶端元素,即当前数组最大值按序放在数组末尾。{ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}
第一个任务即建立大顶堆完成后,第二个任务就很简单了,需要的是将顶端元素输出后(使用swap函数交换),再次调整当前A[1…n-1]序列为大顶端即可。
左侧为swap()过程,右侧为对当前A[1..n-1]序列进行HeapAdjust()过程。
最后数组的排序效果如下:
这里,强调一点,由于数组从A[1]开始存储元素,即声明一个长度为10的数组,有效数据元素个数为9。传入HeapSort()函数的长度为数组长度减一。
最后总结
借鉴书籍:《大话数据结构》
借鉴链接: