排序算法系列(2)——堆排序
堆排序和快速排序一样也是一个O(n logn)的排序算法
但是二者是不一样的实现原理
[这是肯定的，不要pia我]
从分类上来看
快速排序 属于交换排序
堆排序（heap sort）属于选择排序
前些日子接到一个电面，上来就问堆排序，我一脸懵逼，我真的不记得，我只能一脸懵逼的说我不会
超级尴尬有没有！所以为了以后避免这种情况的发生，先好好学堆排序吧。
先说原理：
1. 首先说一下堆
<u>堆heap</u>:
首先逻辑上的结构是一个完全二叉树(如果不知道什么是完全二叉树的可以去百度)
然后按照父节点比子女节点都大/都小 分为大根堆和小根堆（也叫大顶堆 和 小顶堆）
大根堆：该完全二叉树的节点任意一个非叶子节点的value都比它的子女节点大（>=）
小根堆：该完全二叉树的节点任意一个非叶子节点的value都比它的子女节点小（<=）
主要到前面的那个逻辑上了么？
因为目前遇到的堆排序其实很少是在树这个数据结构上进行的(或者说是真正的在java/c中创建一个TreeNode类或者结构体) 而是用数据/list 来存储节点的（特指完全二叉树，因为完全二叉树的结构真的是太完美了）。
哎呀呀，忍不住来说一下一些很简单的数组和完全二叉树的转化
其实就算是当成游戏来找找规律，这个转化也不是很困难，其实数组就是完全二叉树的水平遍历出来的。
然后不难发现在生成的数组中
array[0]其实是相当于树的根节点，然后她的子节点是array[1]和array[2]
array[1]子节点是array[3] array[4]
array[2]子节点是array[5] array[6]
………………………………….....
以此类推
非叶节点的子节点在数组中的体现就是
array[i]的子节点是 array[2i+1]和array[2i+2];
完全二叉树和数组的关系.png
那么
大根堆就是：array[i] >= array[2i+1] && array[i] >= array[2i+2]
小根堆就是：array[i] <= array[2i+1] && array[i] <= array[2i+2]
算法详细解释
根据上面的对于堆的描述我们不难发现，
如果是一个大顶堆，那么根元素是最大的值
如果是一个小顶堆，那么跟元素是最小的值
但是堆也不是<u>有序</u>的，它只能保障节点的值比它的子女们大/小，但是他们子女们的大小顺序是没有保障的
因此需要通过排序，才能实现堆的排序
2. 正式讲堆排序的算法内容：
①、首先构造一个堆，堆排序是建立在堆的基础上的(无序堆)
②、根据构建的堆，将堆中第一个元素(堆顶/根节点)和最后一个元素交换位置
那么最后一个元素就是一个最值，然后排除这个最后一个元素，将剩下的完全二叉树重新调整为堆(无序堆)，重复步骤②，直到只剩下一个元素为止
因此，
如果是以大顶堆来构建 那么最后得到的是水平遍历后是从小到大的完全二叉树(有序小顶堆)
如果是以小顶堆来构建 那么最后得到的是水平遍历后是从大到小的完全二叉树(有序大顶堆)
现在其实核心的算法并不难理解
而且看到重复步骤②这种口吻，我们也不难发现实现原理就是通过递归或者循环的方式
3. 其次要注意的是：
只有在步骤①的时候才会对初始化的数组进行建堆，而在步骤②的每次循环中只需要对堆进行调整(adjust)就可以了，毕竟每次只是将根节点改变，只需要对根节点进行重新调整为一个堆就好，要是还是按照步骤①那样子建堆的话，会浪费很多不必要的逻辑开销。
[具体的建堆和调整堆，下面会慢慢讲，不要着急，心急吃不了热豆腐]
/**
* nums需要排序的堆数组
**/
public void sort(int[] nums){
//首先定义出口 当只剩一个元素的时候 就可以出去了
if(start==(end-1)){
return;
}
//对[start,end)建堆
buildeHeap(nums);
for(int i = nums.length ; i < nums.length ; i--){
//交换 start位置和end-1位置上的值
}
swap()
sort(nums,start,end-1);
}
public void buildHeap(int [] nums){
//coding;
};
那么接下来比较重点的就是如何构建一个最大堆/最小堆以及堆的调整
按照堆排序的思路完整流程走一遍：
建立堆，首先将数组直接按照水平遍历的方式建立一个树：[如下例]
数组int [] nums如下图：
array.png
这个数组先建立一个完全二叉树，如下
c-tree.png
然后开始倒着遍历非叶节点：
根据数组和树之间的映射关系，不难发现，最后一个非叶节点是14那个节点，数数在数组中的index是不是4？ 数组的长度length是不是11？
然后找规律：
不难发现 完全二叉树中（完全二叉树，看清限制条件）
非叶节点的个数 = length/2
叶节点的个数 = (length+1)/2
最后一个非叶节点在对应数组中的index = length/2 - 1
【后来楼主试了一下，前两条性质符合所有的二叉树】
【楼主自认没啥大本事，这种规律记住就好了，以后没准会用这个规律去推其他规律，但是这个规律我是真的不知道咋推出来的了。。。ORZ 有大神可以告知一下】
以构建大根堆为例子：
第一个非叶节点: 以及调整后的情形
1.png
第二个
2.png
第三个[由于满足条件 所以不需要交换]
3.png
4.png
第四个 [换了之后发现，5换后的位置依然不满足要求需要再接着和下层换]
第五个 也就是最后一个：
5.png
这样就构造出来了一个最大堆，我们不难看出来，其实堆并不是有序的，你水平遍历一下就知道，这是无序的，因此这是一个无序堆，但是不论什么堆，只要是堆，那么他的根节点，绝对是一个最值(如本例是最大堆所以顶部就是一个最大值)
然后开始排序吧
首先将根元素和尾元素swap(互换一下)
6.png
如图这样子就相当于排好一个元素了[20]
然后默认从数组中删除最后一个元素[去掉排好序的元素] [对于图中来说不考虑蓝色的节点]
对剩余节点进行调整为堆，但是我们不难发现，由于其他元素在构建堆的时候已经满足堆的需求的了所以没必要从最后一个非叶子节点处进行重构堆，只需要对第一个元素[5] (刚才互换的节点) 进行调整使其满足堆的性质就会又构建成一个堆，因此不难发现，调整比构建堆简单得很。
7.png
然后再把第一个元素和最后一个元素[逻辑概念上就是 19 和 5 , 20还是存在的，只不是过我刚才说过就是你就当它不存在，蓝色都是不存在的，那么第一个节点是19 第二个节点是5 互换了之后如下]
8.png
这样就相当于排好两个元素了，再对剩下的元素(除了蓝色的节点) 如法炮制 -> 调整堆 -> 互换位置 -> 调整堆 -> 互换位置 ………………直到只剩一个元素为止，那么也没有调整的必要了 233333333
<font color=blue>终于讲完了算法了，自己也通了一遍，可以开开心心地写代码了</font>
撸主讲的思路都这么清楚了，代码就一带而过好了，搞懂思路，代码也就比较容易写了。
package HeapSort;
import java.util.Arrays;
import javax.xml.transform.Templates;
/**
* 主要是构建最大堆
* 最后生成从小到大排序的序列
* 算法复杂度为O(N*logN)
* @author mengf
*
*/
public class HeapSort {
public static void main(String[] args) {
HeapSort sort = new HeapSort();
int[] nums = {12,5,17,9,14,13,2,4,19,8,20};
sort.heapSort(nums);
System.out.println(Arrays.toString(nums));
}
/**
* 构建最大堆
* @param nums
*/
public void heapSort(int[] nums){
if (nums.length<=1) {
//数量<=1 的数组排序的意义在哪？ exo me？
//你的良心不会痛么！！！！
return;
}
buildHeap(nums);
//其实都知道调整的次数为多少的
//i 其实就是swap后剩下的节点的个数 也就是length
for(int i = nums.length-1 ; i >= 1 ; i--){
//System.out.println("到这里了");
//swap
swap(nums, i, 0);
//adjust
adjustHeap(nums, 0 ,i);
}
}
private void buildHeap(int[] nums) {
//创建最大堆
int length = nums.length;
//index = n/2 -1 ;
int index = length/2 -1 ;
//最后一个非叶节点的index
//调整为最大堆
for(int i = index ; i >= 0 ; i--){
adjustHeap(nums, i, length);
}
}
/**
*
* @param nums 表示这个数组
* @param i 表示想要调整的对应的位置
* @param length 表示这个堆对应数组的长度 注意不一定是nums的长度哦 ，可能是剩余没排好序的长度
*/
private void adjustHeap(int[] nums,int i,int length){
int left = 2 * i + 1;
int right = 2 * i + 2;
int temp = i;
int tempMax = nums[i];
while (true) {
//System.out.println(temp);
if (right < length && tempMax < nums[right]) {
tempMax = nums[right];
temp = right;
}
if (left < length && tempMax < nums[left]) {
tempMax = nums[left];
temp = left;
}
//如果最大的位置还是i的话 那就不用换了
if (temp == i) {
break;
}else {
swap(nums, temp, i);
//交换完 后 重新初始化 right left 以及默认的位置为i 默认最大值为nums[temp]
left = 2* temp + 1;
right = 2 * temp +2;
i = temp;
tempMax = nums[temp];
}
}
}
private void swap(int nums[], int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
琢磨了好久，都去参考了一下网上的代码才写出来的，看来还是不行，需要多练，懂了原理是一码事情，会践行到代码中又是一件事情，看来要每天写一发了！！
