完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
堆总是满足以下两个特性:
其中,每个结点的值总是不大于其子结点的值,这种堆成为小根堆。
每个结点的值总是不小于其子结点的值,这种堆称为大根堆。
因此,对于一个大根堆R来说,元素R[i](i为元素位置,从0开始)有:
根据堆的性质可知:根结点是最大(或最小)的结点。
因此,对于一个待排序数组可以对数组构造出一个大顶堆,然后将去除最大值的数组再次构造大顶堆,直到待排序序列剩下一个元素为止,每次拿出的数即构成了一个有序序列。
根据上述,排序过程可总结为如下两个操作:
重复上面两个操作,直到堆中只剩下一个结点。
在一个完全二叉树上,对于任意结点R[i],对以R[i]为根结点的树(假设以R[i]的子结点为根节点的树即R[i]的左子树和右子树已经是大顶堆)进行以下操作:
结束后,以R[i]为根结点的树即为一个大顶堆。
对数组[3, 4, 63, 4, 0, 1, 32, -2, 21]构造大顶堆过程如下图所示:
构造大顶堆一般先从树上最后一个非叶子节点开始(上图中深度为3、值为4的节点),然后逐渐遍历树上非叶子节点,直到根节点。也就是说对一个元素个数为 n 的(数组长度为n)的树而言,非叶子节点遍历顺序为: (n-2)/2, ((n-2)/2)-1、((n-2)/2)-2、… 、2、1、0。
详细过程如下图所示:
根据前面对堆排序的介绍,有如下代码。
|
|
在堆排序过程中每轮交换根结点和最后一个结点后的二叉树上,以根结点的子结点为根结点的子树就是一个大顶堆(在堆排序示意图中,第一轮交换后,以根节点4的两个子节点21、32为根节点的子树依然是大顶堆)。
在上边代码中,每轮构造大顶堆时,都是以树上最后一个非叶子结点开始遍历,而树上除根结点外的非叶子结点所构成的树已经是大顶堆,这就造成了没有必要的遍历,增加了循环的次数。
我们可以调整代码逻辑为:首先通过遍历所有的非叶子结点去构造一个大顶堆,然后在以后调整大顶堆过程中都是从根节点开始。
|
|
原文:https://www.cnblogs.com/lijianming180/p/12262602.html