java算法-堆-二叉堆、堆排序
二叉堆
二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆(Max Heap)和最小堆(Min Heap)。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
二叉堆=完全二叉树+排序规则（大顶/小顶规则）。大顶规则：任意父节点值>=子节点值；小顶规则：任意父节点值<=子节点值。所以根节点是整棵树的最大值或最小值。下图展示最大堆（大根堆、大顶堆）、最小堆（小根堆、小顶堆）
二叉堆表示法：
按照《算法4》的说法，二叉堆可以用指针表示二叉堆，每个节点需要三个指针指向其父节点、两个子节点。为了方便，可以利用数组作为二叉堆的存储结构。
定义： 二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个位置）。
如下图所示：
在一个堆中，位置k的结点的父结点的位置为k/2，而它的两个子结点的位置则分别为2k和2k+1，这样在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层就令k等于k/2，向下一层则令k等于2k或2k+1。
堆的算法
我们用长度为N+1的私有数组pq[ ]来表示一个大小为N的堆，我们不会使用pq[0]，堆元素放在pq[1]至pq[N]中。
堆的操作会首先进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。我们称这个过程叫做堆的有序化（reheapifying）。
堆实现的比较和交换方法如下。
/*比较大小，pq[i]是否小于pq[j]？ */
private boolean less(int i ,int j ){
return pq[i].compareTo(pq[j])<0;
}
/* 交换数组的两个元素*/
private void exch(int i,int j){
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
在有序化的过程中我们会遇到两种情况。当某个结点的优先级上升（或是在堆底加入一个新的元素）时，我们需要由下至上恢复堆的顺序。当某个结点的优先级下降（例如，将根结点替换为一个较小的元素）时，我们需要由上至下恢复堆的顺序。首先，我们会学习如何实现这两种辅助操作，然后再用它们实现插入元素和删除最大元素的操作。
由下至上的堆有序化（上浮）：
上浮操作：简言之就是下层插入节点破坏堆有序，需要不断上浮和父节点比较，直至堆有序。
/* 上浮第 k 个元素，以维护最大堆性值 */
private void swim(int k){
while (k>1 && less(k/2,k)){
exch(k/2,k);
k = k/2;
}
}
由上至下的堆有序化（下沉）
下沉操作：简言之，上层某一结点破坏堆有序，需要不断下沉和子节点比较，直到堆有序。
/* 下沉第 k 个元素，以维护最大堆性值 */
private void sink(int k){
//妙！比较k与子节点的大小，同时考虑边界问题
while (2*k <= N){
int j = 2*k;
if (j<N && less(j,j+1)) j++;
if (!less(k,j)) break;
exch(k,j);
k = j;
}
}
插入元素： 我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置
删除最大元素： 我们从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置。
下⾯完整最大堆代码
（PS：为了清晰起⻅，这⾥⽤到 Java 的泛型， Key 可以是任何⼀种可⽐较⼤
⼩的数据类型，你可以认为它是 int、char 等。）
代码：
//大顶堆
public class MaxPQ<Key extends Comparable<Key>> {
//基于堆的完全二叉树
private Key[] pq;
//数据存储在pq[1...N]中，pq[0]不用
private int N = 0;
//maxN为堆最大存储大小，因为pq[0]不用，实例化数组实际大小要加一
public MaxPQ(int maxN){
//注：类型参数"Key"，不能直接实例化
pq = (Key[])new Comparable[maxN+1];
}
public boolean isEmpty(){
return N==0;
}
public int size(){
return N;
}
public void insert(Key v){
N++;
pq[N] = v;
swim(N);
}
public Key delMax(){
//从根节点获得最大元素
Key max = pq[1];
//将最大节点与最后一个节点交换
exch(1,N);
N--;
//方便系统回收它所占用的空间？
pq[N+1] = null;
//恢复堆的有序性
sink(1);
return max;
}
private boolean less(int i ,int j ){
return pq[i].compareTo(pq[j])<0;
}
private void exch(int i,int j){
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
private void swim(int k){
while (k>1 && less(k/2,k)){
exch(k/2,k);
k = k/2;
}
}
private void sink(int k){
//妙！比较k与子节点的大小，同时考虑边界问题
while (2*k <= N){
int j = 2*k;
if (j<N && less(j,j+1)) j++;
if (!less(k,j)) break;
exch(k,j);
k = j;
}
}
//利用大顶堆可方便排序数组
public static void main(String[] args) {
int[] arr = new int[]{1,2,1,2,3,5,1,2,8,3};
MaxPQ<Integer> maxPQ = new MaxPQ<>(arr.length);
for (int i : arr) {
maxPQ.insert(i);
}
for (int i = arr.length-1; i >=0; i--) {
arr[i] = maxPQ.delMax();
}
System.out.println(Arrays.toString(arr));
}
}
堆排序
堆排序可以分为两个阶段：
- 堆的构造：将数组按照最大堆规则构造最大堆。思路是，如果父节点的子节点都堆有序，那么对父节点执行sink()下沉操作，则父节点所在子树堆有序，这样如果对数组从右至左用sink()函数，就能构造堆了。当然只需要从N/2的位置开始就可以，因为最底层无需下沉。
定义： 当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。
- 交换下沉排序： 将堆顶最大值与堆尾调换，这样就排序了一个最大数于数组尾，同时堆大小减一，然后下沉堆顶元素至正确位置以维持堆有序
- 循环执行第二步，直至堆大小为0，这样数组排序成功
（注：这里堆arr[0]存储值，那么a[k]的左右节点为a[2*k+1]、a[2*k+2]，父节点为a[(k-1)/2]）
完整代码：
public class HeapSort {
public int[] sortArray(int[] arr){
heapSort(arr);
return arr;
}
public void heapSort(int[] arr){
int N = arr.length-1;
//1、构造堆
heapify(arr);
//2、交换下沉
//循环不变量 arr[0,N]：堆有序
while (N>0){
swap(arr,0,N);
N--;
sink(arr,0,N);
}
}
private void swap(int[] arr,int i ,int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
/**
* @param arr
* @param k 当前待下称元素下标
* @param N [0,N]是arr的有效部分
*/
private void sink(int[] arr,int k,int N){
while (2*k+1<= N){
int j = 2*k+1;
if (j+1<=N && arr[j]<arr[j+1]) j++;
if (arr[k]<arr[j]){
swap(arr,k,j);
k = j;
}else {
//一定要判断是否满足break，不然会陷入死循环
break;
}
}
}
//将数组整理成堆（堆有序）
private void heapify(int[] arr){
int N = arr.length-1;
for(int k = (N-1)/2;k>=0;k-- ){
sink(arr,k,N);
}
}
}
参考：
《算法 4》、《算法导论》
二叉堆详解实现优先级队列
力扣
PriorityQueue
优先队列待续。。。