堆排HeapSort

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

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

堆：具有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）

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();
	}
}

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

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

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

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

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