堆数据结构和堆排序（Java）
堆的定义（Heap）
public class Heap {
private int[] data;
private int count; //当前节点数
private int capacity; //容量
}
所以，堆中保存数据的就是一个数组
最大堆：根结点的键值是所有堆结点键值中最大者（不仅大于其子节点，同时大于堆中的所有节点值）。每个节点的值都>=其左右孩子（如果有的话）值的完全二叉树。
最小堆：根结点的键值是所有堆结点键值中最小者（同理）。每个节点的值都<=其左右孩子值的完全二叉树。
最大堆的特点：
已知一个节点i，求其左右节点索引和父节点索引
// 左节点下标
public int left(int i) { return i * 2 + 1;}
// 右节点下标
public int right(int i) {return i * 2 + 2;}
// 父节点下标
public int parent(int i) {return (i - 1) / 2;}
输入一个数组Arr实现一个最大堆（完全二叉树）
实现最大堆的算法：
1.把输入的数组赋值给heap对象中的data数组，获取输入数组的长度；
2.建立的最大堆是一个完全二叉树，从完全二叉树最低层最右边的叶子节点的父节点开始，依次向左向上循环检索节点直到根节点；
3.在第2步获取的每一个节点都调用一次shiftDown函数，实现从此节点以下的节点都是最大堆的特性
所以，for循环是自下而上的算法，shiftDown最大堆排序是自上而下的算法。
特点：最大堆的一个父节点的左右节点大小没有顺序，只是两个子节点都比父节点小。
//实现最大堆（用数组来存放完全二叉树中的节点,从上到下,从左到右排序,按序存在数组,子节点的值小于等于父节点的值）
public class Heap {
private int[] data;
private int count; //当前节点数
private int capacity; //容量
public Heap(int capacity) {
this.data=new int[capacity+1]; //因为索引0不存节点，所以长度加一
this.capacity=capacity;
this.count=0;
}
//将一个无序数组构造成一个最大堆：相当于堆排序
public MaxHeap(int[] arr,int n){
data=new int[n+1];
capacity=n;
for(int i=0;i<n;i++){
data[i+1]=arr[i];
}
count=n;
//通过for循环实现所有节点都遍历一遍，而且是从低层的最右边的叶节点的父节点一直从右到左、从下往上索引到根节点。所以，这个算是一个逆向的层次遍历
for(int parent = count/2; parent >= 1; parent--){
shiftDown(parent);
}
}
//调用shiftDown只会从当前节点一直往深度走，往树叶子走而不会同层走，所以这是个深度优先遍历
private void shiftDown(int parent){
int left = 2*parent; // 节点 left 表示 parent父节点对应的左孩子节点
int right = 2*parent+1;
maxValueIndex = left;
while(left <= count){ //有左子节点
if( right <= count && data[right] > data[left]){ // 比较左右子节点那个值更大
maxValueIndex = right;
}
if(data[parent] >= data[maxValueIndex]) //拿父节点和左右子节点更大的进行比较
break;
//如果子节点大于父节点，则交换数据
swap(data,parent,maxValueIndex);
parent = maxValueIndex; //k被赋为当前位置,为下次循环做初始化
}
}
public static void swap(int[] arr,int a,int b){
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
最大堆建立的过程如下图[1]：
最大堆建立过程
利用最大堆实现堆排序
算法思路：
- 先用Heap函数把输入的数组A构造成最大堆。
- 把下标heapSize - 1的元素和下标为0的元素对换，通过减小heapSize，让下标为heapSize - 1的元素从堆中剔除，
- 再调用MaxHeap(heap, 0)即可保证最大堆的性质。
- 重复2和3两个过程，直到堆中只剩下一个元素。
/ * 堆排序
*
* 1. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.
* 2. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n−1]和有序区K[n], 且满足K[1..n−1].keys⩽K[n].key
* 3. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.
*/
public static void heapSort(int[] arr){
for(int i = arr.length; i > 0; i--){
// 把数组中(0,i)之间的索引的数据送入到最大堆函数中实现最大堆
max_heapify(arr, i); //由于i在减小，所以输入的可以操作的数组也在变小，实现了后面排序好的数据的不可操作性
swap(arr, i-1, 0); //堆顶元素(第一个元素)与Kn交换
}
}
private static void max_heapify(int[] arr, int limit){
if(arr.length <= 0 || arr.length < limit) return;
int parentIdx = limit / 2;
//横向层序遍历，从右向左，从下往上，实现把最大的数值往上走，从而实现最大堆
for(; parentIdx >= 0; parentIdx--){
if(parentIdx * 2 >= limit){
continue;
}
int left = parentIdx * 2; //左子节点位置
int right = (left + 1) >= limit ? left : (left + 1); //右子节点位置，如果没有右节点，默认为左节点位置
int maxChildId = arr[left] >= arr[right] ? left : right;
if(arr[maxChildId] > arr[parentIdx]){ //交换父节点与左右子节点中的最大值
swap(arr, maxChildld, parentldx);
}
// 实现了堆中每一个节点值都大于其所有节点值
/*int left = parentldx * 2;
*int right = left + 1
*while(left <= limit){
* right >= limit ? left : (left + 1);
* int maxChildld = arr[left] >= arr[right] ? left : right;
* if(arr[maxChildId] > arr[parentIdx]) swap(arr, maxChildld, parentldx);
* left = parentldx *2;
* right = left + 1;
*}
*/
}
System.out.println("Max_Heapify: " + Arrays.toString(arr));
}
public static void swap(int[] arr,int a,int b){
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
//对排序的实现不一定要让所有节点都大于其节点的节点，我们只要找到一个堆的最大值，然后与数组当前阶段最后面一个值交换便可
//当然，最大堆还是要实现每一个节点都要实现大于其所有子节点
实现的过程图如下：
堆排序实现过程
时间和空间复杂度
时间复杂度
堆排序基本思想是创建最大堆，需要lgn的时间复杂度，同时n中的每一个数都需要操作一遍，所以时间复杂度为nlgn
公式
T(n) = 2T(n/2) + f(n) = 2T(n/2) +Θ(n)
推算过程[5]：
首先要理解怎么计算这个堆化过程所消耗的时间，可以直接画图去理解；
假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；
那么总的时间计算为：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；
S = 2^(k-2) * 1 + 2(k-3)*2.....+2*(k-2)+2(0)*(k-1) ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；
这个等式求解，我想高中已经会了：等式左右乘上2，然后和原来的等式相减，就变成了：
S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)
除最后一项外，就是一个等比数列了，直接用求和公式：S = { a1[ 1- (q^n) ] } / (1-q)；
S = 2^k -k -1；又因为k为完全二叉树的深度，所以 (2^k) <= n < (2^k -1 )，总之可以认为：k = logn （实际计算得到应该是 log(n+1) < k <= logn ）;
综上所述得到：S = n - longn -1，所以时间复杂度为：O(n)
更改堆元素后重建堆时间：O(nlogn)
推算过程：
1、循环 n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：logn(n-1) = nlogn - logn ；
综上所述,堆排序的时间复杂度为：O(nlogn)
空间复杂度
从代码来看，输入的数组的引用直接赋值给了最大堆创建的数组，所以不需要额外n的辅助数组，而每次迭代循环中除了定义的左右孩子节点left, right 和交换数据的tmp，没有其他的变量，此外因为是while循环，所以不存在stack占用过多的递归空间，使用完了就直接出来，所以空间复杂度为O(1).
参考文献：
[1] 堆排序Heap Sort——浅显易懂+Java实现
[2] java实现最大堆及堆排序
[3] java最大最小堆
[4] 八大排序算法总结与java实现
