堆数据结构和堆排序（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]：

最大堆建立过程

利用最大堆实现堆排序

算法思路：

1. 先用Heap函数把输入的数组A构造成最大堆。
2. 把下标heapSize - 1的元素和下标为0的元素对换，通过减小heapSize，让下标为heapSize - 1的元素从堆中剔除，
3. 再调用MaxHeap(heap, 0)即可保证最大堆的性质。
4. 重复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实现