排序(四)堆排序

一、什么是堆

堆是一种非线性结构，（本篇随笔主要分析堆的数组实现）可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲

堆其实就是利用完全二叉树的结构来维护的一维数组

按照堆的特点可以把堆分为大顶堆和小顶堆

大顶堆：每个结点的值都大于或等于其左右孩子结点的值

小顶堆：每个结点的值都小于或等于其左右孩子结点的值

（堆的这种特性非常的有用，堆常常被当做优先队列使用，因为可以快速的访问到“最重要”的元素）

二、堆的特点(数组实现)

我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

三、堆和普通树的区别

内存占用：

普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额外的内存。堆仅仅使用数组，且不使用指针

（可以使用普通树来模拟堆，但空间浪费比较大，不太建议这么做）

平衡：

二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(nlog2n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(nlog2n) 的性能

搜索：

在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作

四、堆排序的过程

先了解下堆排序的基本思想：

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，

如此反复执行，便能得到一个有序序列了，建立最大堆时是从最后一个非叶子节点开始从下往上调整的（这句话可能不好太理解），因为我们希望的是将最大（最小）的值放到根节点，从下往上调整可以使上方的节点能够和最下面的节点比较 .

五、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 堆排序
 * @param a a
 */
public  void  heapSort(int[] a ){
    int i  ,j ,len = a.length ;
    // 每次都会将一个最大值插入到后方
    for (j = 0 ; j < len ; len --){
        //遍历所有拥有子节点的节点 ， 将最大值放入父节点，遍历完所有父节点则根节点就是最大值
        for (i= len / 2 - 1 ; i>=0 ; i--){
            //左节点 
            if (a[2*i+1] > a[i]){
                swap(a,2*i+1 , i);
            }
            //右节点
            if (2*i+2 < len && a[2*i+2] > a[i]){
                swap(a,2*i+2 , i);
            }
        }
        //将根节点插入到后方
        swap(a,0,len-1);
    }
}