牛骨文教育服务平台(让学习变的简单)

堆排序是一种树形选择排序,是对直接选择排序的有效改进。

堆的构建--》堆排:

初始状态-<从最后一个结点开始,使该子树成堆(最小/大的数移到根节点),不断循环>-初始堆(小/大顶)--输出堆顶元素(堆顶与堆的最后一个元素交换位置)--最后一个数移至堆顶--重新建--输出堆顶元素

以下为《数据结构(C++版)习题解答与实验指导》实例

1、算法思想

堆:具有n个元素的序列(k1,k2,...,kn),当且仅当满足

时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(最大项)。
若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

(a)大顶堆序列:(96, 83,27,38,11,09)

(b)小顶堆序列:(12,36,24,85,47,30,53,91)

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序。

因此,实现堆排序需解决两个问题:

  1. 如何将n 个待排序的数建成堆;
  2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。

首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。
调整大顶堆的方法:

1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

2)将根结点与左、右子树中较大元素的进行交换。

3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

称这个自 根结点 到 叶子结点 的调整过程为筛选。如图:

再讨论对n 个元素初始建堆的过程。
建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

1)n 个结点的完全二叉树,则最后一个结点是第
个结点的子树。【向下取整】

2)筛选从第
个结点为根的子树开始,该子树成为堆。

3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)

2、代码实现

package sort;

public class HeapSort {
	public static void main(String[] args) {
		int[] src = { 66, 89, 8, 123, 9, 44, 55, 37, 200, 127, 98 };
		System.out.println("初始值:");
		print(src);
		HeapSort(src, src.length);
		System.out.println("堆排后:");
		print(src);
	}

	/**
	 * 大顶堆排序算法
	 */
	private static void HeapSort(int src[], int length) {// 大顶堆排序算法
		// 初始化堆,从最后一个节点 i= (length-1) / 2
		for (int i = (length - 1) >> 1; i >= 0; --i)
			HeapAdjust(src, i, length);
		for (int i = length - 1; i > 0; --i) {// 从堆尾往前调整
			src[i] = src[0] + (src[0] = src[i]) * 0;// 弹出堆顶最大值,堆尾值填补
			HeapAdjust(src, 0, i);// 重新调整堆
		}
	}

	/**
	 * src[i+1,…. ,j]已经成堆,调整 i 的子树为堆.
	 * 
	 * @param src是待调整的堆数组
	 * @param i是待调整的数组元素的位置
	 * @param j是待调整数组的长度
	 */
	private static void HeapAdjust(int src[], int i, int j) {// 对下标为i的节点,调整其子树为堆
		int temp = src[i];
		int child = 2 * i + 1; // 左孩子的位置。(child+1 为当前调整结点的右孩子的位置)
		while (child < j) {// 防止第一次length为偶数12时,i=5与child=11非父子关系
			if (child + 1 < j && src[child] < src[child + 1]) { // 定位较大的的孩子结点
				++child;
			}
			if (src[i] < src[child]) { // 如果较大的子结点大于父结点
				src[i] = src[child]; // 那么把较大的子结点往上移动,替换它的父结点
				i = child; // 更新i,以便使新子树为堆(子树结构可能改变)
				src[i] = temp; // 父结点放到比它大的孩子结点上(temp值未变)
				child = 2 * i + 1;// 若child<length,则继续循环建堆
			} else { // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出
				break;// 防止死循环
			}
		}
		print(src);
	}

	private static void print(int a[]) {
		for (int i : a) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
}

3、算法分析

堆排序也是一种不稳定的排序算法。 

堆排序优于简单选择排序的原因:

直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。

堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。

堆排序在最坏的情况下,其时间复杂度也为O(nlogn)。相对于快速排序来说,这是堆排序的最大优点。此外,堆排序仅需一个记录大小的供交换用的辅助存储空间。

建堆时对于每个非终端结点来说,其实最多进行两次比较和互换操作,比较次数不超过4n 次,因此整个构建堆的时间复杂度为O(n)。

设树深度为k
,从根到叶的筛选,元素比较次数至多2(k-1)次,交换记录至多k 次。所以,在建好堆后,排序过程中的筛选次数不超过下式:

因此堆排序最坏情况下,时间复杂度也为:O(nlogn )

4、算法改进

堆排序可通过树形结构保存部分比较结果,可减少比较次数。

源码地址:https://github.com/zxiaofan/Algorithm/blob/master/src/sort/HeapSort.java