2018-04-19 堆排序java
上一遍中，学习了树形选择排序，https://www.jianshu.com/p/b20ed599ac07
树形选择结构在相比于普通的选择排序确实在时间复杂度上提升很多，但树形选择排序还有一些可以改进的地方，它需要很多额外的存储空间（对长度为n的数组排序，需要申请2n-1长度的数组空间）。所以有人在此基础上提出了“堆”的概念，创立了堆排序。
堆
定义：堆是一种特殊的二叉树结构，如果一颗完全二叉树的每个节点都不大于（不小于）它的子节点就可以称为堆。
（完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树 ）
1.小根堆
若一个节点存在左右子节点且该节点的值小于左右子节点的值则称为小根堆。
2.大根堆
若一个节点存在左右子节点且该节点的值大于左右子节点的值则称为大根堆。
堆排序
堆排序的大体脉络为：对无序的数据先建成堆，输出堆顶元素，然后以最后一个元素来代替堆顶元素，然后再进行调整，使之仍然为一个堆
以小根堆为例（演示建堆过程）
无序数组 [6, 10, 2, 5, 7, 1, 4, 8, 3, 9]
1，先将无序数组以从上到下，从左到右的顺序放入完全二叉树中
1.jpg
2，填充完毕，开始建堆过程
①所有的叶子节点都满足堆要求，因为叶子页面没有子节点，所以不需要跟子节点比较。
②那么我们就从最后一个非叶子节点开始，这里就是7, 7小于子节点9，满足堆要求。
③再向前看5，不满足堆要求，跟较小的子树交换，5和3交换。
④再向前看2，不满足堆要求，跟较小的子树交换，2和1交换。
⑤再向前看10，不满足堆要求，跟较小的子树交换，10和5交换。10跟5换下来后，破坏了下边已经满足要求的子树，然后10继续和3交换。
⑥然后1和6交换，6和2再交换，这样堆就建成了。
流程图如下：
2.jpg
3， 进入第二阶段，从堆中输出堆顶元素，输出1，然后将最后一个元素提拔到根节点。
123.png
4 此时显而易见的，现在除了提拔上来根节点外，其他节点都满足堆的要求，则需要对9进行调整，跟右子树2交换，然后再跟左子树6交换，直到9落地到最底层为止。
4.png
5，一直循环直到将堆中的数据输出完成。
到这里以上基本上堆排序的逻辑就分析完成。还算比较容易理解。
.----------------------------------------------------------------------------------------------------------------------------------------------
.----------------------------------------------------------------------------------------------------------------------------------------------
JAVA代码实现堆排序
根据上边分析，从原理上看，堆排序是用二叉树的结构来表示，但在实际应用中，我们可以用1维数组来表示一个完全二叉树。
Untitled.png
标出数组下边，并且将下标以从上到下，从左到右的方式填入到完全二叉树的节点中。
通过上图，我们分析二叉树中的节点的父子关系。
假如节点下标为 k，则
父节点：(k-1)/2
左孩子：2 * k + 1
右孩子：2 * k + 2
总结：这样看来，用数组来表示完全二叉树是没有问题的，因为通过当前数组下标，可以通过简单数学公式计算出父节点，子节点所在位置。
通过java代码来实现堆排序
package test;
public class MyA {
//节点k进行筛选
//a:堆数据, n:堆中有效数据个数, k:待筛选节点(数组下标)
static void heapOne(int[] a, int n, int k)
{
int k1 = 2 * k + 1;
int k2 = 2 * k + 2;
if (k1>=n && k2>=n) return; //判断k是否为叶子节点
int a1 = Integer.MAX_VALUE;
int a2 = Integer.MAX_VALUE;
if(k1<n) a1=a[k1]; // 左孩子值
if(k2<n) a2=a[k2]; // 右孩子值
if (a[k]<=a1&&a[k]<=a2) return; // 已经符合堆得要求
//找到左右孩子中最小的，和它交换
if(a1<a2) {
int t=a[k];
a[k] = a[k1];
a[k1] = t;
heapOne(a, n, k1); // 继续筛选子树
} else {
int t = a[k];
a[k] = a[k2];
a[k2] = t;
heapOne(a, n, k2); //继续筛选子树
}
}
static void heapSort(int[] a)
{
// 获取父节点方式 (k-1)/2
// 建立初始堆
for(int i=(a.length-1)/2;i>=0;i--)
heapOne(a, a.length, i);
// 边输出堆顶， 边调整
int n = a.length; // 剩余元素数
while (n > 0) {
System.out.print(a[0] + " "); // 输出堆顶元素
a[0] = a[n-1]; // 最后一个元素移动到堆顶
n--;
heapOne(a, n, 0);
}
System.out.println();
}
public static void main(String[] args)
{
int[] a = {12,3,6,8,5,19,20,16,4,2,7,13,13,11};
heapSort(a);
}
}
非递归方式实现堆排序。
先创建大根堆，然后用根元素（根元素此时为最大值）跟最后一个元素交换，重新调整元素，使之满足堆得要求
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class HeapSort2 {
public static void main(String[] args) {
// 定义整型数组
int[] arr = {1,5,6,8,7,2,3,4,9};
// 调用堆排序
heapSort(arr);
// 输出排序后的数组
System.out.println(Arrays.toString(arr));
}
private static void heapSort(int[] arr) {
int n = arr.length - 1;
for (int parent = (n-1)/2; parent >= 0; parent--) {
// 构造大根堆，从下往上构造
// i为最后一个根节点(最后一个非叶子节点)，n为数组最后一个元素的下标
heapOne(arr, parent, n);
}
//
for (int i=n; i > 0; i--) {
// 把最大的数，也就是堆顶元素和最后一个元素交换(这样最大数就放到最后了)
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapOne(arr, 0, i-1);
}
}
private static void heapOne(int[] arr, int parent, int n) {
// 定义临时变量存储父节点中的数据，防止被覆盖
int temp = arr[parent];
//2*parent+1是其左孩子节点
for(int i=parent*2+1;i<=n;i=i*2+1)
{
//如果左孩子大于右孩子，就让i指向右孩子,沿节点较大的子节点向下调整
if(i<n && arr[i]<arr[i+1])
{
i++;
}
//如果父节点大于或者等于较大的孩子，那就退出循环
if(temp>=arr[i])
{
break;
}
//如果父节点小于孩子节点，那就把孩子节点放到父节点上
arr[parent] = arr[i];
//把孩子节点的下标赋值给parent
//让其继续循环以保证大根堆构造正确
parent = i;
}
//将刚刚的父节点中的数据赋值给新位置
arr[parent] = temp;
}
}
