:-: 14.9 堆排序 * * * * * 首先我们先认识什么是堆？ n个元素的序列{k1,k2,k3,k4,........,kn}，当且仅当满足以下下列关系时，成为堆： :-:  如果将序列看成一个完全二叉树，则非终端结点的值均小于或大于左右子结点的值。 最大堆和最小堆的图片示例：堆顶元素为最大值或为最小值。堆是存放在线性空间里面的，是不过利用了树的结构特征来描述堆。 :-:  **基本概念：** （Heapsort）它是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。是在树形选择排序的基础上的优化（消除了树形选择排序的辅助存储空间较多，并且需要和“最大值”进行多余的比较的缺点）。 **算法的运作** 1、将无序序列建成一个堆：若是有n个元素的序列，首先构建成树，然后从n/2个元素开始，到第一个元素结束，进行反复筛选，构建成为堆。（筛选过程：从第n/2元素(父节点)开始与它的两个子节点，三者选取最大值（最小值），做父节点，如果原父节点是最大值（最小值），则子结构不变，然后从下一个元素继续筛选，如果左子节点或右子节点是最大值（最小值），则此子节点的值与原父节点的值做交换，成为新的父子节点，构建成为新的子结构，然后从下一个元素继续筛选，直到第一个元素筛选后结束） 2、输出堆顶的最大值（最小值），与堆中最后一个元素交换位置，同时使得处理的序列范围减一。 3、将剩下的n - 1个元素重复上述步骤，重新调整为一个新的堆，筛选出新的次最大值（最小值）。 4、最后会得到一个新的序列（从大到小或从小到大）。 **图片示例：** :-:  **代码实现：** ~~~ /** * 堆排序的主要入口方法，共两步。 */ public static void sort(int[] arr) { /* * 第一步：将数组堆化 beginIndex = 第一个非叶子节点。 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。 * 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。 */ int len = arr.length - 1; int beginIndex = (len - 1) >> 1; for (int i = beginIndex; i >= 0; i--) { maxHeapify(arr, i, len); } /* * 第二步：对堆化数据排序 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。 * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。 直至未排序的堆长度为 0。 */ for (int i = len; i > 0; i--) { swap(arr, 0, i); maxHeapify(arr, -0, i - 1); } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /** * 调整索引为 index 处的数据，使其符合堆的特性。 * @param index 需要堆化处理的数据的索引 * @param len 未排序的堆（数组）的长度 */ private static void maxHeapify(int[] arr, int index, int len) { int li = (index << 1) + 1; // 左子节点索引 int ri = li + 1; // 右子节点索引 int cMax = li; // 子节点值最大索引，默认左子节点。 if (li > len) return; // 左子节点索引超出计算范围，直接返回。 if (ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。 cMax = ri; if (arr[cMax] > arr[index]) { swap(arr, cMax, index); // 如果父节点被子节点调换， maxHeapify(arr, cMax, len); // 则需要继续判断换下后的父节点是否符合堆的特性。 } } ~~~ **复杂度分析：** 时间复杂度：平均：O(nlogn)、最坏：O(nlogn)、最优：O(nlogn)。 空间复杂度：最坏：O(n)。 **为什么选择位置为n/2的元素开始？** 完全二叉树的性质，假设有n个叶子节点，所以假设高度为h,2^h-1 = n,所以有2h = 2n,对于满二叉树，节点数为2h - 1 = 2n - 1。又已知叶子节点个数为n。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。** **本文主要参考以下文章：** [数据结构排序ppt：提取码：270s](https://pan.baidu.com/s/10WWKUT-VQZ2foCfhIWWMSQ) [维基百科——最大，最小堆](https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E2%80%94%E6%9C%80%E5%B0%8F%E5%A0%86) [维基百科——堆排序](https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F) [选择排序（树形选择排序，堆排序）这个堆排序过程是错误的,留作参考](http://zhouyunan2010.iteye.com/blog/1217462) [堆排序.gif（图片来源）](https://github.com/Sir814/Sort/blob/master/07.%E5%A0%86%E6%8E%92%E5%BA%8F.gif)